Zur MathePrisma-Startseite
Zur Modul-Startseite  


Turingmaschine (Theorie 3)
 

 
 
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:
 
Die Churchsche These
 
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:
 
Und nochmal die Chursche These
 
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.
 
Seite 13/17