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:

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

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.