Die Church-Turing-These besagt, dass jede Funktion, die intuitiv "berechenbar" ist, auch mit einer Turing- Maschine berechnet werden kann.

Jedes algorithmische Problem, das in irgendeiner Programmiersprache programmiert und auf irgendeinem dafür geeigneten Computer ausgeführt werden werden (sogar auf Computern, die noch nicht gebaut sind, aber prinzipiell gebaut werden könnten), und selbst wenn es unbeschränkt viel Zeit und Speicherplatz für immer grössere Eingaben benötigt - jedes solche Programm ist auch durch eine Turing-Maschine lösbar.

Several versions of the thesis appear in the literature, some stronger, some weaker. It can be broken down into two parts: first, that a problem that cannot be solved through any theoretical means of computatinn that is, a Turing machine, cannot be solved by human thought either; second, that if humans can solve a problem or engage in some intelligent activity, then machines can ultimately be constructed to perform in the same way.

Church-Turing-These, öffentliche Version: 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 existiert ein endliches FlooP-Programm (d. h. eine allgemein rekursive Funktion), das genau die gleichen Antworten gibt wie die Methode des vernunftbegabten Wesens.

Die Church-Turing-These ist sicher eines der wichtigsten Konzepte in der Philosophie der Mathematik, des Gehirns und des Denkens.

Ich persönlich bin durchaus bereit, die ursprüngliche mathematische Form der Church-Turing-These zu akzeptieren. Hingegen ist ihre Beziehung zum Verhalten realer physikalischer Systeme ein anderes Thema, das uns in diesem Buch später noch intensiv beschäftigen wird.

Heutzutage sind Computer mit hohen Rechengeschwindigkeiten so alltäglich, daß anscheinend kaum jemand diese These in ihrer ursprünglichen Form anzweifeln mag. Das Interesse hat sich eher der Frage zugewandt, ob physikalische - das heißt exakten physikalischen Gesetzen gehorchende - Systeme (zu denen das menschliche Gehirn vermutlich gehört) bei der Ausführang logischer und mathematischer Operationen einer Turing-Maschine überlegen, unterlegen oder genau gleichwertig sind.