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

pg-System unfähig, irgendwelche andere Eigenschaften natürlicher Zahlen auszudrücken, geschweige denn zu repräsentieren. Deshalb wäre es in einem Wettstreit zwischen Systemen, die für die Zahlentheorie in Frage kommen, ein sehr schwacher Kandidat.
    Nun hat TNT den Vorzug, daß sich in ihm praktisch jedes zahlentheoretische Prädikat ausdrücken läßt; zum Beispiel läßt sich leicht eine TNT-Kette niederschreiben, die das Prädikat „ b hat die Schildkröten-Eigenschaft“ ausdrückt. Was also die Kraft, etwas auszudrücken, angeht, so ist TNT alles, was wir benötigen.
    Indessen ist die Frage: „Welche Eigenschaften sind in TNT repräsentiert?“ genau die Frage: „Was leistet TNT als Axiomensystem?“ Sind alle möglichen Prädikate in TNT repräsentiert? Wenn ja, dann kann TNT jede zahlentheoretische Frage beantworten; es ist vollständig.
Primitiv-rekursive Prädikate sind in TNT repräsentiert
    Obgleich sich Vollständigkeit als Schimäre entpuppen wird, ist TNT zumindest im Hinblick auf primitiv-rekursive Prädikate vollständig. In anderen Worten: jede Aussage der Zahlentheorie, deren Wahrheit oder Unwahrheit von einem Computer in einer voraussagbaren Zeitspanne entschieden werden kann, ist auch innerhalb von TNT entscheidbar. Oder, als abschließende Neuformulierung des gleichen Sachverhalts:
    Wenn ein BlooP-Test für eine Eigenschaft der natürlichen Zahlen niedergeschrieben werden kann, dann ist diese Eigenschaft in TNT repräsentiert.
Gibt es Funktionen, die nicht primitiv-rekursiv sind?
    Nun sind die Eigenschaften, die durch BlooP-Tests entdeckt werden können, äußerst vielfältiger Natur, z. B. ob eine Zahl prim oder perfekt ist, die Goldbach-Eigenschaft besitzt, eine Potenz von 2 ist usw. Die Frage, ob jede Eigenschaft der Zahlen mit einem passenden BlooP-Programm aufgefunden werden kann, wäre keineswegs abwegig. Daß wir im gegenwärtigen Augenblick keine Methode besitzen, um zu testen, ob eine Zahl wundersam ist oder nicht, braucht uns nicht allzusehr zu beunruhigen, denn das könnte einfach bedeuten, daß wir zu wenig über Wundersamkeit wissen, und wenn wir noch tiefer graben, könnten wir eine Universalformel für die Obergrenze der betreffenden Schleife entdecken. Dann könnte man sofort einen BlooP-Test niederschreiben. Ähnliches ließe sich auch über die Schildkröten-Eigenschaft sagen.
    In Wirklichkeit lautet die Frage also: „Können immer obere Grenzen für die Länge der Rechenoperation angegeben werden, oder wohnt dem System der natürlichen Zahlen eine Art Verwirrung inne, die es mitunter unmöglich macht, vorauszusagen, wie lang die Rechenoperation werden wird?“ Bemerkenswerterweise ist das letztere der Fall, und wir werden gleich sehen, warum. Es ist von der Art, was Pythagoras, der als erster bewiesen hat, daß die Quadratwurzel von 2 irrational ist, in den Wahnsinn getrieben hätte. In unserem Beweis machen wir von der berühmten, von Georg Cantor, dem Begründer der Mengenlehre, erfundenen Diagonalmethode Gebrauch.
Der Pool B, Indexzahlen und Blaue Programme
    Wir beginnen damit, daß wir einen kuriosen Begriff einführen: den Vorrat aller möglichen BlooP-Programme. Natürlich ist dieser Vorrat — „Pool B“ genannt — unendlich. Wir wollen einen Teilvorrat von Pool B, den wir durch drei sukzessive Filteroperationen erhalten, betrachten. Der erste Filter wird für uns nur aufruflose Programme zurückhalten. Von diesem Teilvorrat eliminieren wir alle Tests und lassen nur Funktionen übrig. (Übrigens entscheidet bei aufruflosen Programmen die letzte Prozedur in der Kette, ob das Programm als Ganzes als Test oder als Programm aufzufassen ist.) Der dritte Filter hält nur Funktionen zurück, die genau einen Input-Parameter besitzen. (Auch das bezieht sich auf die abschließende Prozedur in der Kette.) Was bleibt übrig?
    Ein vollständiger Vorrat aller aufruflosen BlooP-Programme, die Funktionen von genau einem Input-Parameter berechnen.
    Nennen wir diese speziellen BlooP-Programme Blaue Programme.
    Wir würden nun gerne jedem Blauen Programm eine eindeutige Indexzahl zuordnen. Wie geht das vor sich? Der leichteste Weg — welchen wir einschlagen werden —ist der, sie nach ihrer Länge zu ordnen: das kürzestmögliche Blaue Programm wäre Nr. 1, das zweitkürzeste Nr. 2 usw. Natürlich wird es viele Programme gleicher Länge geben. In solchen Fällen halten wir uns an die alphabetische Ordnung. ,,Alphabetische Ordnung“ ist hier in einem erweiterten Sinn zu