Die Church-Turing-These

 
Wir haben im letzten Abschnitt gesehen, wie eine DTM eine Funktion berechnet und haben mehrere Beispiele gesehen, wie eine DTM spezielle Funktionen berechnet. Man kann sich vielleicht bereits vorstellen, dass neben der Addition und der Subtraktion auch alle anderen Rechenoperationen möglich sind, die ein Mensch auf einem Papier machen kann. Im Grunde genommen folgt jede Rechnung, die ein Mensch auf einem Papier machen kann, einer genauen Vorschrift und ist damit ein Algorithmus. Dies lässt sich dann auch in eine Turingmaschine kodieren, die damit alles machen kann, was ein Mensch machen kann. Die Church-Turing-These, die wir eingangs schon erwähnten, besagt genau dies. Sie ist so bedeutend, dass sie uns diesen eigenen Abschnitt wert ist. Die Church-Turing-These besagt folgendes:

Alles was intuitiv berechenbar ist, d.h. alles, was von einem Menschen berechnet werden kann, das kann auch von einer Turingmaschine berechnet werden. Ebenso ist alles, was eine andere Maschine berechnen kann, auch von einer Turingmaschine berechenbar.

Für uns von besonderer Bedeutung ist auch der Umkehrschluss:

Was eine Turingmaschine nicht berechnen kann, kann auch kein Mensch berechnen!

Da die Turingmaschine ein formales Modell ist, kann man exakt argumentieren, was diese nicht kann bzw. versuchen dies zu tun. Gelingt dies, so hat man eine Funktion gefunden, die auch ein Mensch nicht berechnen kann. Wir werden später sehen, dass sich hier ganz grundlegende Problemstellungen der Informatik verstecken, die einer algorithmischen Lösung also nicht zugänglich sind.

 
 

Hier ein paar Fragen zur Church-Turing-These.