Ich pr\u00e4sentiere Ihnen eine \u00dcbersetzung der ersten Seiten von Alan Turings Artikel – \u201e\u00dcBER BERECHNBAREN ZAHLEN MIT ANWENDUNG AUF DAS AUFL\u00d6SUNGSPROBLEM\u201c 1936. Die ersten Kapitel enthalten eine Beschreibung von Computern, die sp\u00e4ter die Grundlage f\u00fcr die moderne Informatik bildeten.<\/p>\n
Die vollst\u00e4ndige \u00dcbersetzung des Artikels und der Erkl\u00e4rung kann im Buch des amerikanischen Popularisierers Charles Petzold mit dem Titel \u201eReading Turing\u201c nachgelesen werden. Eine Reise durch Turings wegweisenden Artikel \u00fcber Berechenbarkeit und Turing-Maschinen. (ISBN 978-5-97060-231-7, 978-0-470-22905-7)<\/p>\n
Originalartikel: —<\/p>\n \u00dcBER BERECHNBARE ZAHLEN MIT ANWENDUNG AUF DAS AUFL\u00d6SUNGSPROBLEM<\/p>\n A. M. TURING<\/p>\n [Eingegangen am 28. Mai 1936 \u2013 gelesen am 12. November 1936]<\/p>\n Berechenbare Zahlen k\u00f6nnen kurz als reelle Zahlen beschrieben werden, deren Ausdr\u00fccke als Dezimalbr\u00fcche auf endlich viele Arten berechnet werden k\u00f6nnen. Obwohl dieser Artikel Zahlen auf den ersten Blick als berechenbar behandelt, ist es fast genauso einfach, berechenbare Funktionen einer ganzzahligen Variablen, einer reellen Variablen, einer berechenbaren Variablen, berechenbarer Pr\u00e4dikate und dergleichen zu definieren und zu untersuchen. Die grundlegenden Probleme, die mit diesen berechenbaren Objekten verbunden sind, sind jedoch jeweils dieselben. F\u00fcr eine detaillierte Betrachtung habe ich berechenbare Zahlen als berechenbares Objekt gew\u00e4hlt, da die Methode, sie zu ber\u00fccksichtigen, am wenigsten umst\u00e4ndlich ist. Ich hoffe, bald die Beziehung zwischen berechenbaren Zahlen und berechenbaren Funktionen usw. beschreiben zu k\u00f6nnen. Gleichzeitig wird auf dem Gebiet der Theorie der Funktionen einer reellen Variablen, ausgedr\u00fcckt in berechenbaren Zahlen, geforscht. Nach meiner Definition ist eine reelle Zahl berechenbar, wenn ihre Darstellung als Dezimalbruch von einer Maschine geschrieben werden kann.<\/p>\n In den Abs\u00e4tzen 9 und 10 gebe ich einige Argumente an, um zu zeigen, dass berechenbare Zahlen alle Zahlen umfassen, von denen man nat\u00fcrlich annimmt, dass sie berechenbar sind. Insbesondere zeige ich, dass einige gro\u00dfe Zahlenklassen berechenbar sind. Dazu geh\u00f6ren beispielsweise die Realteile aller algebraischen Zahlen, die Realteile der Nullstellen von Bessel-Funktionen, die Zahlen \u03c0, e und andere. Allerdings umfassen berechenbare Zahlen nicht alle definierbaren Zahlen, wie das folgende Beispiel einer definierbaren Zahl zeigt, die nicht berechenbar ist.<\/p>\n Obwohl die Klasse der berechenbaren Zahlen sehr gro\u00df ist und in vielerlei Hinsicht der Klasse der reellen Zahlen \u00e4hnelt, ist sie dennoch aufz\u00e4hlbar. In \u00a78 betrachte ich bestimmte Argumente, die gegenteilig zu sein scheinen. Bei richtiger Anwendung eines dieser Argumente ergeben sich Schlussfolgerungen, die auf den ersten Blick denen von G\u00f6del* \u00e4hneln. Diese Ergebnisse haben \u00e4u\u00dferst wichtige Anwendungsm\u00f6glichkeiten. Insbesondere kann, wie unten gezeigt (\u00a711), das Aufl\u00f6sungsproblem nicht gel\u00f6st werden.<\/p>\n In seinem j\u00fcngsten Artikel f\u00fchrte Alonzo Church** die Idee der \u201eeffektiven Berechenbarkeit\u201c ein, die meiner Vorstellung von \u201eBerechenbarkeit\u201c entspricht, aber eine v\u00f6llig andere Definition hat. Zu \u00e4hnlichen Schlussfolgerungen kommt auch Church hinsichtlich der L\u00f6sungsproblematik. Der Beweis der \u00c4quivalenz von \u201eBerechenbarkeit\u201c und \u201eF\u00e4higkeit, effektiv gez\u00e4hlt zu werden\u201c wird im Anhang dieses Artikels vorgelegt.<\/p>\n 1. Computer<\/p>\n Wir haben bereits gesagt, dass berechenbare Zahlen diejenigen Zahlen sind, deren Dezimalstellen mit endlichen Mitteln abz\u00e4hlbar sind. Hier ist eine klarere Definition erforderlich. Dieser Artikel wird keinen wirklichen Versuch unternehmen, die hier gegebenen Definitionen zu rechtfertigen, bis wir zu \u00a79 kommen. Vorerst m\u00f6chte ich nur anmerken, dass der (logische) Grund (daf\u00fcr) darin besteht, dass das menschliche Ged\u00e4chtnis zwangsl\u00e4ufig begrenzt ist.<\/p>\n Vergleichen wir eine Person, die gerade eine reelle Zahl berechnet, mit einer Maschine, die nur eine endliche Anzahl von Bedingungen q1, q2, …, qR erf\u00fcllen kann; Nennen wir diese Bedingungen \u201eM-Konfigurationen\u201c. Diese (also so definierte) Maschine ist mit einem \u201eBand\u201c (analog zu Papier) ausgestattet. Dieses durch die Maschine laufende Band ist in Abschnitte unterteilt. Nennen wir sie \u201eQuadrate\u201c. Jedes dieser Quadrate kann eine Art \u201eSymbol\u201c enthalten. Zu jedem Zeitpunkt gibt es nur ein solches Quadrat, sagen wir das r-te, das das Symbol \u201ein dieser Maschine\u201c enth\u00e4lt. Nennen wir ein solches Quadrat ein \u201egescanntes Symbol\u201c. Ein \u201egescanntes Zeichen\u201c ist das einzige Zeichen, das der Maschine sozusagen \u201edirekt bekannt\u201c ist. Durch \u00c4ndern seiner M-Konfiguration kann sich die Maschine jedoch effektiv an einige der Zeichen erinnern, die sie zuvor \u201egesehen\u201c (gescannt) hat. Das m\u00f6gliche Verhalten der Maschine zu jedem Zeitpunkt wird durch die m-Konfiguration qn und das gescannte Symbol*** bestimmt. Nennen wir dieses Symbolpaar qn, \u201eKonfiguration\u201c. Die so bezeichnete Konfiguration bestimmt das m\u00f6gliche Verhalten einer bestimmten Maschine. In einigen dieser Konfigurationen, in denen das gescannte Quadrat leer ist (dh kein Zeichen enth\u00e4lt), schreibt das Ger\u00e4t ein neues Zeichen auf das gescannte Quadrat und in anderen dieser Konfigurationen l\u00f6scht es das gescannte Zeichen. Diese Maschine ist auch in der Lage, sich zu bewegen, um ein anderes Quadrat zu scannen, auf diese Weise kann sie sich jedoch nur zu dem benachbarten Quadrat rechts oder links bewegen. Zus\u00e4tzlich zu diesen Vorg\u00e4ngen kann die M-Konfiguration der Maschine ge\u00e4ndert werden. In diesem Fall bilden einige der geschriebenen Zeichen eine Ziffernfolge, die den Dezimalteil der zu berechnenden reellen Zahl darstellt. Der Rest wird nichts weiter als ungenaue Markierungen sein, um \u201edem Ged\u00e4chtnis zu helfen\u201c. In diesem Fall k\u00f6nnen nur die oben genannten ungenauen Markierungen gel\u00f6scht werden.<\/p>\n Ich behaupte, dass die hier betrachteten Operationen alle Operationen umfassen, die in der Berechnung verwendet werden. Die Begr\u00fcndung dieser Aussage ist f\u00fcr den Leser, der sich mit der Maschinentheorie auskennt, leichter zu verstehen. Daher werde ich im n\u00e4chsten Abschnitt die betreffende Theorie weiter entwickeln, basierend auf einem Verst\u00e4ndnis der Bedeutung der Begriffe \u201eMaschine\u201c, \u201eBand\u201c, \u201egescannt\u201c usw. Ich pr\u00e4sentiere Ihnen eine \u00dcbersetzung der ersten Seiten von Alan Turings Artikel – \u201e\u00dcBER BERECHNBAREN ZAHLEN MIT ANWENDUNG AUF DAS AUFL\u00d6SUNGSPROBLEM\u201c 1936. Die ersten Kapitel enthalten eine Beschreibung von Computern, die sp\u00e4ter die Grundlage f\u00fcr die moderne Informatik bildeten. Die vollst\u00e4ndige \u00dcbersetzung des Artikels und der Erkl\u00e4rung kann im Buch des amerikanischen Popularisierers Charles PetzoldContinue reading “Turing-Rechenmaschinen”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61],"tags":[180],"class_list":["post-3057","post","type-post","status-publish","format-standard","hentry","category-techie","tag-turing-machine","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"de","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/3057","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/comments?post=3057"}],"version-history":[{"count":20,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/3057\/revisions"}],"predecessor-version":[{"id":3890,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/posts\/3057\/revisions\/3890"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/media?parent=3057"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/categories?post=3057"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/de\/wp-json\/wp\/v2\/tags?post=3057"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
https:\/\/www.astro.puc.cl\/~rparra\/tools\/PAPERS\/turing_1936.pdf<\/a><\/p>\n
*G\u00f6del \u201e\u00dcber die formal unentscheidbaren S\u00e4tze der Principia Mathematics (ver\u00f6ffentlicht von Whitehead und Russell 1910, 1912 und 1913) und verwandte Systeme, Teil I\u201c, Journal of Mathematics. Physik, Monatsheft Nr. 38 (f\u00fcr 1931, S. 173-198.
** Alonzo Church, \u201eAn Undecidable Problem in Elementary Number Theory\u201c, American J. of Math., Nr. 58 (1936), S. 345-363.
*** Alonzo Church, \u201eA Note on the Problem of Resolution\u201c, J. of Symbolic Logic, Nr. 1 (1936), S. 40-41<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"