Church-Turing-These

Die Church-Turing-These (auch Churche These, benannt nach Alonzo Church und Alan Turing) ist eine These der Berechenbarkeitstheorie. Sie geht davon aus, dass eine gewisse Vorstellung davon existiert, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Allerdings ist es schwierig bis unmöglich auf Basis dieser Intuition den Nachweis zu führen, dass eine Funktion nicht berechenbar ist.

Der intuitive Begriff der Berechenbarkeit muss daher mittels einer Definition in eine mathematische Form gebracht werden. Dadurch kann es ermöglicht werden, von einer Funktion nachzuweisen, dass sie nicht berechenbar ist. Allerdings muss begründet werden, dass die formale Definition den intuitiven Begriff der Berechenbarkeit erfasst. Diese Begründung mündet dann in der Church-Turing-These:

Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen.

Diese These ist nicht beweisbar, da der Begriff intuitiv berechenbare Funktion nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auch von einem Menschen ausgerechnet werden könnten. Es wird in der Informatik üblicherweise angenommen, dass die These stimmt.

Entstehung

Turing empfand die Gedankenprozesse eines Menschen beim Zahlenrechnen durch die von ihm entwickelte Turingmaschine nach (in der Funktionsweise ähnlich den heutigen Computern) und analysierte deren Fähigkeiten [1]. Er stellte fest, dass viele Funktionen, die von einem Menschen ausgedacht werden können, erst gar nicht durch die Turingmaschine berechenbar sind, wie z.B. die Funktion des Halteproblems.

Zum anderen zeigte sich, dass auch andere Herangehensweisen, die menschliche Denkweise beim Rechnen zu formalisieren nicht erfolgreicher waren: So wurde von Turing historisch zuerst die Äquivalenz von Churchs Lambdakalkül zur Turingmaschine bewiesen. Es folgten darauf viele weitere vorgeschlagene Algorithmenbegriffe, die alle in ihrer Berechnungsfähigkeit nicht mehr leisteten als die Turingmaschine. Man bezeichnet sie demzufolge als turing-vollständig.

Dies ließ vermuten, dass es keinen mächtigeren Formalismus als den der Turingmaschine hinsichtlich der Berechenbarkeit gäbe und der Mensch - ebenfalls algorithmisch arbeitend - auch nicht mehr Funktionen ausrechnen könne. Damit entstand die Church-Turing-These.

Implikationen

Falls die These wahr ist, kann es kein Rechenmodell geben, das mehr als die bisherigen Modelle berechnen kann. Insbesondere ist ein Computer ein solches Rechenmodell, somit kann auf ihm theoretisch jeder Algorithmus ausgeführt werden, vorausgesetzt genügend Speicherplatz ist vorhanden. Es ist dann nicht möglich eine Rechenmaschine zu bauen, die mehr berechnen kann als ein Computer bereits kann. Da viele Programmiersprachen ebenfalls turing-vollständig sind, kann man jeglichen Algorithmus mittels eines Quelltexts dieser Sprachen ausdrücken.

Falls die These falsch ist, gelten die genannten Implikationen nicht. Eine Widerlegung der These wäre mit der Konstruktion eines Hypercomputers möglich, der Berechnungen ausführen kann, die auf einer Turingmaschine nicht möglich sind.

Weitere Algorithmenbegriffe

partiell-rekursive Funktion
Registermaschine
Markow-Algorithmus
GOTO-Programm
LOOP-Programm (nicht turing-vollständig)
WHILE-Programm

Referenzen und Literatur

Siehe auch: Gödelscher Unvollständigkeitssatz, Philosophie des Geistes