Gödel, Escher, Bach - ein Endloses Geflochtenes Band

Zeile 5. Hier ist m = 30.
    R EGEL 2: Wenn wir 3 × 10 m + n erzeugt haben, können wir 10 m × (3 × 10 m + n ) + n erzeugen.
    Beispiel: Übergang von Zeile 1 zu Zeile 2, wobei sowohl m und n gleich 1 sind.
    R EGEL 3: Wenn wir k × 10 m +3 + 111 × 10 m + n erzeugt haben, dann können wir k × 10 m +1 + n erzeugen.
    Beispiel: Übergang von Zeile 3 zu Zeile 4. Hier sind m und n gleich 1 und k ist 3.
    R EGEL 4: Wenn wir k × 10 m +2 + n erzeugt haben, dann können wir k × 10 m + n erzeugen.
    Beispiel: Übergang von Zeile 6 zu Zeile 7. Hier ist m = 2, n = 10 und k = 301.
    Vergessen wir nicht unser Axiom! Ohne das kommen wir nicht weiter. Statuieren wir also:
    Wir können 31 erzeugen.
    Nun läßt sich die rechte Kolonne als ein vollständiger arithmetischer Prozeß auffassen, in einem neuen arithmetischen System, das wir das 310-System nennen könnten:
1)
31
gegeben
2)
311
Regel 2 ( m = 1, n = 1)
3)
31111
Regel 2 ( m = 2, n = 11)
4)
301
Regel 3 ( m = 1, n = 1, k = 3)
5)
3010
Regel 1 ( m = 30)
6)
3010010
Regel 2 ( m = 3, n = 10)
7)
30110
Regel 4 ( m = 2, n = 10, k = 301)
    Man beachte auch hier, daß die Verlängerungs- und Verkürzungsregeln in diesem „310-System“ immer noch vorhanden sind; sie sind einfach in den Zahlenbereich transponiert worden, so daß die Gödel-Nummern steigen und sinken. Bei sorgfältigerBeobachtung dieser Vorgänge wird man entdecken, daß die Regeln auf nichts tiefgründigerem beruhen, als auf der Vorstellung, daß die Verschiebung von Ziffern nach links und nach rechts in der Dezimaldarstellung von ganzen Zahlen der Multiplikation mit und der Division durch Zehnerpotenzen verwandt ist. Diese einfache Beobachtung findet ihre Verallgemeinerung in der folgenden
    Z ENTRAL -A USSAGE : Wenn es eine typographische Regel gibt, die sagt, wie bestimmte Ziffern in einer im Dezimalsystem dargestellten Zahl verschoben, verändert, weggelassen oder eingefügt werden können, dann läßt sich die Regel genauso gut durch eine arithmetische Entsprechung darstellen, die arithmetische Operation mit Zehnerpotenzen sowie Addition, Subtraktion usw. enthält.
    Kürzer:
    Typographische Regeln für die Manipulation von Zahlzeichen sind in Wirklichkeit arithmetische Regeln für das Operieren mit Zahlen.
    Diese einfache Beobachtung ist der Kern von Gödels Methode, und sie wird eine absolut zerschmetternde Wirkung haben. Sie sagt uns, daß, wenn wir eine Gödel-Numerierung für irgendein formales System haben, wir sofort eine Anzahl arithmetischer Regeln bilden können, die die Gödel-Isomorphie vervollständigen. Das Ergebnis ist, daß wir das Studium eines formalen Systems — ja sogar aller formalen Systeme — in die Zahlentheorie übertragen können.
MIU-erzeugbare Zahlen
    Genauso wie irgendeine Menge von typographischen Regeln eine Menge von S ÄTZEN erzeugt, erzeugt die wiederholte Anwendung arithmetischer Regeln eine entsprechende Menge von natürlichen Zahlen. Diese erzeugbaren Zahlen spielen in der Zahlentheorie dieselbe Rolle wie die S ÄTZE innerhalb eines formalen Systems. Natürlich sind verschiedene Zahlen erzeugbar, je nachdem, welche Regeln man anwendet. „Erzeugbare Zahlen“ sind aber nur im Hinblick auf ein System arithmetischer Regeln erzeugbar. Zum Beispiel könnte man Zahlen wie 31, 3010010, 31111 usw. als MIU-erzeugbare Zahlen bezeichnen — eine unbeholfene Bezeichnung, die wir auf MIU-Zahlen verkürzen können. Das symbolisiert die Tatsache, daß diese Zahlen diejenigen sind, die sich ergeben, wenn man das MIU-System via Gödel-Numerierung in die Zahlentheorie transponiert. Wenn wir das pg-System Gödel-numerierten und dann seine Regeln arithmetisierten, könnten wir die erzeugbaren Zahlen „pg-Zahlen“ nennen — usw.
    Man beachte, daß die erzeugbaren Zahlen (in irgendeinem gegebenen System) durch eine rekursive Methode definiert werden: Sind Zahlen gegeben, von denen wir wissen, daß sie erzeugbar sind, haben wir Regeln, die uns sagen, wie wir weitere erzeugbare Zahlen herstellen können. So erweitert sich konstant die Klasse der Zahlen, von denen wir wissen, daß sie erzeugbar sind, ganz ähnlich, wie das die Liste der Fibonacci-Zahlen oder der Q-Zahlen tat. Die Menge der erzeugbaren Zahlen in jedemSystem ist eine rekursiv aufzählbare. Wie steht es mit dem Gegenstück — der Menge der nicht erzeugbaren Zahlen? Ist diese Menge immer rekursiv aufzählbar? Haben Zahlen, die nicht erzeugbar sind, eine gemeinsame arithmetische Eigenschaft?
    Beim Studium der Transponierung von formalen