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

bewiesen. Eng damit verwandt ist ein anderer, ich nenne ihn den
    T ARSKI -C HURCH -T URING -S ATZ : Es gibt keine unfehlbare Methode zur Unterscheidung von wahren und falschen Aussagen in der Zahlentheorie.
Die Church-Turing-These
    Zum besseren Verständnis von Churchs Satz und dem Tarski-Church-Turing-Satz müssen wir zuerst eine der Ideen beschreiben, auf denen diese Sätze beruhen, und das ist die Church-Turing-These (oft „Church-These“ genannt), denn die Church-Turing-These ist sicher eines der wichtigsten Konzepte in der Philosophie der Mathematik, des Gehirns und des Denkens.
    Die Church-Turing-These kann — wie Tee — in verschiedenen Stärken serviert werden. Ich werde also verschiedene Varianten vorlegen, und wir werden uns Gedanken darüber machen, was sie bedeuten.
    Die erste Variante klingt ganz harmlos, beinahe nichtssagend:
    C HURCH -T URING -T HESE , TAUTOLOGISCHE V ERSION : Mathematische Probleme kann man nur lösen, wenn man Mathematik betreibt.
    Die Bedeutung liegt natürlich in der Bedeutung der einzelnen Bestandteile. Unter einem „mathematischen Problem“ verstehe ich das Problem, zu entscheiden, ob eine gewisse Zahl eine bestimmte arithmetische Eigenschaft besitzt oder nicht. Es erweist sich, daß fast alle Probleme in jedem Zweig der Mathematik mittels Gödel-Numerierung und verwandten Codierungstricks in diese Form gebracht werden können, so daß „mathematisch“ seine übliche Bedeutung beibehält. Wie steht es mit „Mathematik treiben“? Versucht man festzustellen, ob eine Zahl eine gewisse Eigenschaft besitzt, dann gibt es offensichtlich nur eine kleine Anzahl von Operationen, die man immer und immer wieder in Kombination verwendet — Addition, Multiplikation, Prüfung auf Gleichheit oder Ungleichheit. Das heißt: das einzige uns zur Verfügung stehende Mittel für die Erforschung der Zahlenwelt scheinen aus diesen Operationen gebildete Schleifen zu sein. Man beachte das Wort „scheinen“: Das ist das kritische Wort, um das sich die Church-Turing-Tarski-These dreht. Nun können wir eine revidierte Fassung angeben:
    C HURCH -T URING -T HESE , S TANDARDVERSION : Angenommen, es gibt eine Methode, die ein vernunftbegabtes Wesen anwendet, um Zahlen in zwei Klassen zu sortieren. Angenommen zudem, daß diese Methode eine Antwort immer in einer endlichen Zeitspanne ergibt und daß sie für eine bestimmte Zahl immer die gleiche Antwort ergibt. Dann gibt es ein endliches FlooP-Programm (d. h. eine allgemein rekursive Funktion), das genau die gleiche Antwort ergibt wie die Methode des vernunftbegabten Wesens.
    Die grundlegende Hypothese — um das ganz klar zu machen — ist die, daß jeder Denkprozeß, der die ganzen Zahlen in zwei Arten aufteilt, in der Form eines FlooP-Programms beschrieben werden kann. Intuitiv kann man glauben, daß es keine anderen Werkzeuge als die in FlooP gibt und daß es keine anderen Methoden für den Gebrauch dieser Werkzeuge gibt als unbeschränkte Wiederholungen (die in FlooP zugelassen sind). Die Church-Turing-These ist nicht eine beweisbare Tatsache in dem Sinn wie ein Satz in der Mathematik — sie ist eine Hypothese über die Vorgänge im menschlichen Gehirn.
Die „öffentliche“ Variante
    Nun hat mancher vielleicht das Gefühl, daß diese Variante zuviel behauptet. Die Einwände könnten etwa so lauten: „Jemand wie der Krebs könnte existieren — jemand mit beinahe mystischen Einsichten in die Mathematik, der aber über seine eigenen Fähigkeiten genau so im Dunkel wäre wie jeder andere — und die Denkmechanismen dieser Person könnten vielleicht Operationen durchführen, die in FlooP keine Entsprechung haben.“ Dahinter steht die Vorstellung, daß wir vielleicht ein unbewußtes Potential für die Ausführung von Dingen haben, die die bewußten Prozesse transzendieren — Dinge, die sich durch die elementaren FlooP-Operationen nicht ausdrücken lassen. Für die, die diese Einwände vorbringen, geben wir eine schwächere Version der These, eine, die zwischen öffentlichen und privaten Denkprozessen unterscheidet:
    C HURCH -T URING -T HESE , ÖFFENTLICHE V ERSION : Angenommen, es gibt eine Methode, die ein vernunftbegabtes Wesen anwendet, um Zahlen in zwei Klassen zu sortieren. Weiter sei angenommen, daß diese Methode in einer endlichen Zeitspanne immer eine Antwort liefert. Bedingung: Angenommen wird außerdem, daß diese Methode zuverlässig von einem vernunftbegabten Wesen einem anderen vermittels der Sprache mitgeteilt werden kann. Dann