Author Archives: demensdeum

Ich präsentiere Ihnen eine Übersetzung der ersten Seiten von Alan Turings Artikel – „ÜBER BERECHNBAREN ZAHLEN MIT ANWENDUNG AUF DAS AUFLÖSUNGSPROBLEM“ 1936. Die ersten Kapitel enthalten eine Beschreibung von Computern, die später die Grundlage für die moderne Informatik bildeten.

Die vollständige Übersetzung des Artikels und der Erklärung kann im Buch des amerikanischen Popularisierers Charles Petzold mit dem Titel „Reading Turing“ nachgelesen werden. Eine Reise durch Turings wegweisenden Artikel über Berechenbarkeit und Turing-Maschinen. (ISBN 978-5-97060-231-7, 978-0-470-22905-7)

Originalartikel:
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf

—

ÜBER BERECHNBARE ZAHLEN MIT ANWENDUNG AUF DAS AUFLÖSUNGSPROBLEM

A. M. TURING

[Eingegangen am 28. Mai 1936 – gelesen am 12. November 1936]

Berechenbare Zahlen können kurz als reelle Zahlen beschrieben werden, deren Ausdrücke als Dezimalbrüche auf endlich viele Arten berechnet werden können. 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ädikate und dergleichen zu definieren und zu untersuchen. Die grundlegenden Probleme, die mit diesen berechenbaren Objekten verbunden sind, sind jedoch jeweils dieselben. Für eine detaillierte Betrachtung habe ich berechenbare Zahlen als berechenbares Objekt gewählt, da die Methode, sie zu berücksichtigen, am wenigsten umständlich ist. Ich hoffe, bald die Beziehung zwischen berechenbaren Zahlen und berechenbaren Funktionen usw. beschreiben zu können. Gleichzeitig wird auf dem Gebiet der Theorie der Funktionen einer reellen Variablen, ausgedrückt in berechenbaren Zahlen, geforscht. Nach meiner Definition ist eine reelle Zahl berechenbar, wenn ihre Darstellung als Dezimalbruch von einer Maschine geschrieben werden kann.

In den Absätzen 9 und 10 gebe ich einige Argumente an, um zu zeigen, dass berechenbare Zahlen alle Zahlen umfassen, von denen man natürlich annimmt, dass sie berechenbar sind. Insbesondere zeige ich, dass einige große Zahlenklassen berechenbar sind. Dazu gehören beispielsweise die Realteile aller algebraischen Zahlen, die Realteile der Nullstellen von Bessel-Funktionen, die Zahlen π, e und andere. Allerdings umfassen berechenbare Zahlen nicht alle definierbaren Zahlen, wie das folgende Beispiel einer definierbaren Zahl zeigt, die nicht berechenbar ist.

Obwohl die Klasse der berechenbaren Zahlen sehr groß ist und in vielerlei Hinsicht der Klasse der reellen Zahlen ähnelt, ist sie dennoch aufzählbar. In §8 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ödel* ähneln. Diese Ergebnisse haben äußerst wichtige Anwendungsmöglichkeiten. Insbesondere kann, wie unten gezeigt (§11), das Auflösungsproblem nicht gelöst werden.

In seinem jüngsten Artikel führte Alonzo Church** die Idee der „effektiven Berechenbarkeit“ ein, die meiner Vorstellung von „Berechenbarkeit“ entspricht, aber eine völlig andere Definition hat. Zu ähnlichen Schlussfolgerungen kommt auch Church hinsichtlich der Lösungsproblematik. Der Beweis der Äquivalenz von „Berechenbarkeit“ und „Fähigkeit, effektiv gezählt zu werden“ wird im Anhang dieses Artikels vorgelegt.

1. Computer

Wir haben bereits gesagt, dass berechenbare Zahlen diejenigen Zahlen sind, deren Dezimalstellen mit endlichen Mitteln abzählbar sind. Hier ist eine klarere Definition erforderlich. Dieser Artikel wird keinen wirklichen Versuch unternehmen, die hier gegebenen Definitionen zu rechtfertigen, bis wir zu §9 kommen. Vorerst möchte ich nur anmerken, dass der (logische) Grund (dafür) darin besteht, dass das menschliche Gedächtnis zwangsläufig begrenzt ist.

Vergleichen wir eine Person, die gerade eine reelle Zahl berechnet, mit einer Maschine, die nur eine endliche Anzahl von Bedingungen q1, q2, …, qR erfüllen kann; Nennen wir diese Bedingungen „M-Konfigurationen“. Diese (also so definierte) Maschine ist mit einem „Band“ (analog zu Papier) ausgestattet. Dieses durch die Maschine laufende Band ist in Abschnitte unterteilt. Nennen wir sie „Quadrate“. Jedes dieser Quadrate kann eine Art „Symbol“ enthalten. Zu jedem Zeitpunkt gibt es nur ein solches Quadrat, sagen wir das r-te, das das Symbol „in dieser Maschine“ enthält. Nennen wir ein solches Quadrat ein „gescanntes Symbol“. Ein „gescanntes Zeichen“ ist das einzige Zeichen, das der Maschine sozusagen „direkt bekannt“ ist. Durch Ändern seiner M-Konfiguration kann sich die Maschine jedoch effektiv an einige der Zeichen erinnern, die sie zuvor „gesehen“ (gescannt) hat. Das mögliche Verhalten der Maschine zu jedem Zeitpunkt wird durch die m-Konfiguration qn und das gescannte Symbol*** bestimmt. Nennen wir dieses Symbolpaar qn, „Konfiguration“. Die so bezeichnete Konfiguration bestimmt das mögliche Verhalten einer bestimmten Maschine. In einigen dieser Konfigurationen, in denen das gescannte Quadrat leer ist (dh kein Zeichen enthält), schreibt das Gerät ein neues Zeichen auf das gescannte Quadrat und in anderen dieser Konfigurationen löscht 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ätzlich zu diesen Vorgängen kann die M-Konfiguration der Maschine geändert 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 „dem Gedächtnis zu helfen“. In diesem Fall können nur die oben genannten ungenauen Markierungen gelöscht werden.

Ich behaupte, dass die hier betrachteten Operationen alle Operationen umfassen, die in der Berechnung verwendet werden. Die Begründung dieser Aussage ist für den Leser, der sich mit der Maschinentheorie auskennt, leichter zu verstehen. Daher werde ich im nächsten Abschnitt die betreffende Theorie weiter entwickeln, basierend auf einem Verständnis der Bedeutung der Begriffe „Maschine“, „Band“, „gescannt“ usw.

*Gödel „Über die formal unentscheidbaren Sätze der Principia Mathematics (veröffentlicht von Whitehead und Russell 1910, 1912 und 1913) und verwandte Systeme, Teil I“, Journal of Mathematics. Physik, Monatsheft Nr. 38 (für 1931, S. 173-198.
** Alonzo Church, „An Undecidable Problem in Elementary Number Theory“, American J. of Math., Nr. 58 (1936), S. 345-363.
*** Alonzo Church, „A Note on the Problem of Resolution“, J. of Symbolic Logic, Nr. 1 (1936), S. 40-41