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

Entscheidend ist, daß es verschiedene ganz und gar natürliche Methoden gibt, um algorithmische Sprachen zu erfinden, und verschiedene Menschen, die verschiedene Wege einschlagen, kommen üblicherweise zur Erzeugung gleichwertiger Sprachen, wobei der einzige Unterschied im Stil liegt, nicht in der Leistungsfähigkeit.
... ist ein Mythos
    Tatsächlich ist der Glaube weit verbreitet, daß es zur Beschreibung von Berechnungen keine leistungsfähigere Sprache gebe als Sprachen, die gleichwertig mit FlooP sind. Diese Hypothese sprachen unabhängig voneinander zwei Forscher in den dreißiger Jahren aus: Alan Turing, auf den wir später zurückkommen werden, und Alonzo Church, einer der hervorragendsten Logiker unseres Jahrhunderts. Man nennt sie die Church-Turing-These. Wenn wir die CT-These akzeptieren, dann müssen wir schließen, daß „GlooP“ ein Mythos ist — in FlooP gibt es keine Einschränkungen, die es zu beseitigen gälte, keine Methode zur Steigerung der Leistungsfähigkeit durch „Entfesselung“, wie wir das mit BlooP taten.
    Das versetzt uns in die unangenehme Lage, behaupten zu müssen, daß ein Mensch Rotdiag [ N ] für jeden Wert von N berechnen kann, daß es aber keine Methode zur Programmierung eines Computers gibt. Denn wenn es überhaupt gemacht werden könnte, könnte es in FlooP getan werden — und auf Grund seiner Konstruktion kann es nicht in FlooP getan werden. So eigenartig ist diese Schlußfolgerung, daß sie uns veranlassen sollte, die Stützen, auf denen sie ruht, sehr sorgfältig zu prüfen. Und eine davon war, wie der Leser sich erinnern wird, unsere wacklige Annahme, daß es ein Entscheidungsverfahren gibt, das endende und nicht-endende FlooP-Programme zu unterscheiden vermag. Bereits die Vorstellung eines solchen Entscheidungsverfahrens schien verdächtig, als wir sahen, daß ihre Existenz es gestatten wird, alle Probleme der Zahlentheorie auf einheitliche Weise zu lösen. Nun haben wir doppelten Grund zu glauben, daß jeder Endend?-Test ein Mythos ist — daß es keine Methode gibt, FlooP-Programme in eine Zentrifuge zu werfen und die Endenden von den Nicht-Endenden zu trennen.
    Ein Skeptiker könnte behaupten, daß wir weit davon entfernt sind, einen strikten Beweis dafür gegeben zu haben, daß es keinen Endend?-Test gibt. Das ist ein gültiger Einwand; indessen zeigt Turings Ansatz noch zwingender, daß in einer Sprache der FlooP-Klasse kein Computerprogramm abgefaßt werden kann, das einen Endend?-Test bei allen FlooP-Programmen durchführen kann.
Die Church-Turing-These
    Kommen wir noch einmal auf die Church-Turing-These zurück. Über sie und über Variationen von ihr werden wir in Kapitel XVII sehr ausführlich sprechen; im Augenblick wird es genügen, sie in einigen Versionen vorzuführen und eine Diskussion ihrer Vorteile und Ihrer Bedeutung bis dann zu verschieben. Hier also drei miteinander verwandte Arten, die CT-These zu formulieren:
1)
Was Menschen berechnen können, können Maschinen berechnen.
2)
Was Maschinen berechnen können, kann mit FlooP berechnet werden.
3)
Was Menschen berechnen können, kann mit FlooP berechnet werden (d. h. allgemein oder partiell rekursiv).
Terminologie: allgemein und partiell rekursiv
    Wir haben in diesem Kapitel eine ziemlich breit angelegte Übersicht über gewisse zahlentheoretische Begriffe und ihre Beziehungen zur Theorie berechenbarer Funktionen gegeben. Das ist ein weites und reiches Feld, eine anziehende Mischung zwischen Computerwissenschaft und moderner Mathematik. Wir sollten dieses Kapitel nicht beschließen, ohne die Standard-Terminologie für die Begriffe, mit denen wir uns beschäftigen, einzuführen.
    Wie bereits erwähnt, ist „BlooP-berechenbar“ gleichbedeutend mit „primitiv-rekursiv“. Nun können FlooP-berechenbare Funktionen in zwei Arten unterteilt werden: 1) diejenigen, die durch endende FlooP-Programme berechnet werden können: man nennt sie allgemein-rekursiv, und 2) diejenigen, die nur durch nicht-endende FlooP-Programme berechnet werden können: man nennt sie partiell rekursiv. (Das gleiche gilt für Prädikate.) Man sagt häufig „rekursiv“, wenn man „allgemein-rekursiv“ meint.
Die Leistungsfähigkeit von TNT
    Interessant ist, daß TNT so leistungsfähig ist, daß in ihm nicht nur alle primitiv-rekursiven Prädikate repräsentiert sind, sondern darüber hinaus alle allgemein-rekursiven Prädikate. Wir werden diese beiden Tatsachen nicht beweisen, da diese Beweise angesichts unseres Ziels, zu