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

bestimmen können, zu welcher Klasse ein FlooP-Programm gehört, hätte das erstaunliche Folgen, wie wir bald sehen werden. Ich brauche nicht zu sagen, daß die Operation der Überprüfung der Klasse selbst eine endende Operation sein muß — sonst wäre nichts gewonnen!
Turings Tricks
    Es könnte uns einfallen, diese Inspektion einer BlooP-Prozedur zu übertragen. BlooP-Prozeduren jedoch können nur mit Zahlen, nicht aber mit Programmen gespeist werden. Das können wir aber umgehen ... indem wir Programme in Zahlen codieren! Dieser schlaue Trick ist einfach eine Gödelisierung in einer anderen ihrer vielfältigen Erscheinungsweisen. Geben wir den 56 Zeichen des FlooP-Alphabets die „Codons“ 901, 902, ... 956, so erhält jedes FlooP-Programm eine sehr lange Gödel-Nummer. Zum Beispiel erhielte die kürzeste BlooP-Funktion (die auch ein endendes FlooP-Programm ist)
    PROZEDURDEFINITION „A“ [B]:
    BLOCK 0: ANFANG
    BLOCK 0: ENDE
    die nachstehend teilweise abgedruckte Gödel-Nummer:
916, 
918, 
915, 
926, 
905, 
904, 
921, 
918, 
 ..... 
905, 
914, 
904, 
905, 
955
P
R
O
Z
E
D
U
R
 ..... 
E
N
D
E
.
    Nun ist unser Plan der, einen BlooP-Test namens ENDEND? zu schreiben, der JA sagt, wenn seine Input-Zahl ein endendes FlooP-Programm codiert, und wenn nicht, NEIN . So könnten wir die Aufgabe einer Maschine übertragen und, wenn wir Glück haben, die Endenden von den Nicht-Endenden unterscheiden. Indessen zeigt ein von Alan Turing vorgebrachtes geistreiches Argument, daß kein BlooP-Programm diese Unterscheidung unfehlbar treffen kann. Im Grunde ist der Trick fast der gleiche wie der von Gödel, und deshalb eng mit Cantors Diagonaltrick verwandt. Wir werden ihn hier nicht vorführen; es genügt, wenn wir sagen, daß der Grundgedanke der ist, dem Endend?-Tester seine eigene Gödel-Nummer einzugeben. Das ist gar nicht so einfach, denn es entspricht dem Versuch, einen ganzen Satz innerhalb seiner selbst zu zitieren. Man muß das Zitat zitieren usw.; das führt anscheinend zu einem unendlichen Regreß. Turing jedoch fand einen Trick, um einem Programm seine eigene Gödel-Nummer einzuspeisen. Eine Lösung desselben Problems in einem anderen Zusammenhang werden wir im nächsten Kapitel geben. Im vorliegenden Kapitel werden wir einen anderen Weg zum gleichen Ziel einschlagen, nämlich zu dem Beweis, daß ein Endend?-Tester unmöglich ist. Lesern, die eine elegante und einfache Darstellung von Turings Ansatz wünschen, empfehle ich den Artikel von Hoare und Allison, „Incomputability“, in: Computing Surveys Nr. 4 , September 1972.
Ein Endend?-Tester wäre Zauberei
    Bevor wir diese Vorstellung demolieren, wollen wir darlegen, warum ein Endend?-Tester eine so bemerkenswerte Angelegenheit wäre. In einem gewissen Sinn wäre das, als besäße man eine magische Wünschelrute, die alle zahlentheoretischen Probleme mit einer einzigen FluuT wegschwemmen könnte. Nehmen wir zum Beispiel an, wir wollten wissen, ob die Goldbach-Variation eine wahre Vermutung ist oder nicht. Das heißt: haben alle Zahlen die Schildkröten-Eigenschaft? Wir würden damit beginnen, einen FlooP-Test namens SCHILDKRÖTE? niederzuschreiben, der prüft, ob sein Input die Schildkröten-Eigenschaft aufweist. Nun verwandelt sich der Mangel dieser Prozedur — nämlich daß sie nicht zu Ende geht, wenn die Schildkröten-Eigenschaft fehlt hier in eine Tugend! Denn jetzt lassen wir den Endend?-Tester mit der Prozedur SCHILDKRÖTE? laufen. Wenn dabei JA herauskommt, so bedeutet das, daß SCHILDKRÖTE? für alle Input-Werte abbricht — in anderen Worten, alle Zahlen haben die Schildkröten-Eigenschaft. Wenn NEIN herauskommt, dann wissen wir, daß es eine Zahl gibt, die die Achilles-Eigenschaft besitzt. Eine gewisse Ironie liegt darin, daß wir vom Programm SCHILDKRÖTE? keinen Gebrauch machen — wir inspizieren es nur.
    Die Vorstellung, ein zahlentheoretisches Problem zu lösen, indem man es in eine Zahl codiert und dann einen Endend?-Tester über das Programm schwingt, ist nicht ganz unähnlich der Idee, einen Kōan auf seine Echtheit zu prüfen, indem man ihn in einen gefalteten Faden codiert und dann einen Test für Buddha-Natur statt dessen auf dem Faden ausführt. Wie Achilles vorschlug, liegt vielleicht die gewünschte Information in der einen Repräsentation „näher an der Oberfläche“ als in einer anderen.
Pool F, Indexzahlen und Grüne Programme
    Nun, genug der Tagträume! Wie können wir beweisen, daß der Endend?-Tester unmöglich