Die Turingmaschine

Die Turingmaschine ist ein universelles Automatenmodell. Sie wurde 1936 von dem Mathematiker Alan Turing vorgeschlagen. Es handelt sich dabei um ein Maschinenmodell.

Aufbau

Eine Turingmaschine hat ein Band, welches in einzelne Felder unterteilt ist. Zusätzlich gibt es einen Lese-/Schreibkopf. In jedem Feld des Bandes kann genau ein Zeichen stehen oder es kann leer sein.

Funktionsweise

Es kann immer nur genau das Feld gelesen und neu beschrieben werden, welches sich gerade unter dem Lese-/Schreibkopf befindet. Danach kann der Lese-/Schreibkopf (bzw. das Band) um eine Stelle nach rechts oder links bewegt werden.

Zur Steuerung dieser Aktionen (Schreiben und Bewegen) besitzt die Turingmaschine eine endliche Menge von Zuständen und eine Zustandsübergangstabelle. Die Zustandsübergangstabelle stellt aktuelle und mögliche Zustände dar.

Churchsche These

1936 formulierte der amerikanische Mathematiker und Logiker Alonzo Church die nach ihm benannte Churchsche These. Sie besagt:

Die Klasse der turingberechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.

Diese These ist nicht beweisbar, aber in der Informatik wird sie im Allgmeinen anerkannt. Man kann die These weiterentwicklen zu der folgenden Aussage:

Eine Funktion ist genau dann (turing- oder intuitiv) berechenbar, wenn sie durch ein Programm implementiert werden kann.