Die Turingmaschine ist das allgemeinste Konzept.
Die Arbeitsweise der Turingmaschine ist vergleichbar mit der eines Menschen oder einer Maschine, wenn sie Symbole auf einem Blatt Papier oder in einem elektronischen Speicher manipulieren.
In jedem Arbeitsschritt wird ein Zeichen entsprechend eines vorgegebenen Programms gelesen und überschrieben. Danach bewegt sich der Lese/Schreibkopf um ein Feld nach rechts oder links oder hält an.
Bis heute ist kein berechenbares Problem bekannt, das nicht bereits mit der Turingmaschine lösbar wäre. Daher gilt die Churchsche These mittlerweile als akzeptiert:
Alles was überhaupt (intuitiv) berechenbar ist, ist schon mit der Turingmaschine berechenbar.
Da die Churchsche These einen intuitiven Berechenbarkeitsbegriff verwendet, ist sie nicht beweisbar!
Beachte die Mächtigkeit der Aussage. Sie lässt sich nämlich auch so formulieren:
Alles was mit der Turingmaschine nicht berechenbar ist, lässt sich überhaupt nicht berechnen.
Und dabei sind nicht nur Computer gemeint, die momentan entwickelt werden, sondern auch alle, die jemals konstruiert werden. (Vorausgesetzt sie lesen und schreiben Zeichen auf einem Speicher.)
Anwendbarkeit
Die zweite Formulierung wird verwendet, wenn bewiesen werden soll, dass etwas nicht berechenbar ist. Es reicht dann nämlich zu zeigen, dass es mit der Turingmaschine nicht zu berechnen ist.
