Übersicht Automaten
5. Turingmaschine
Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes mathematisches Modell.
Die Turingmaschine besteht aus- einem unendlich langen Speicherband mit unendlich vielen Feldern. In jedem dieser Felder kann genau ein Zeichen gespeichert werden.
- einem Schaltwerk mit endlich vielen Zuständen. Es steuert das Verhalten der Turingmaschine.
- einem programm-gesteuerten Lese- und Schreibkopf, der auf dem endlosen Speicherband ein Feld nach links oder rechts rücken, ein Zeichen lesen, schreiben oder löschen und stehen bleiben kann.
Das faszinierende an einer Turing-Maschine ist, dass sie mit nur 3 Operationen (lesen, schreiben und Kopf bewegen) alle lösbaren Probleme lösen kann. Sämtliche mathematischen Grundfunktionen, wie Addition und Multiplikation lassen sich mit diesen 3 Operatoren simulieren. Aufbauend darauf lassen sich wiederum sämtliche restlichen vorhandenen mathematischen Funktionen erzeugen, usw.
Der zentrale Satz ist also: Ein Problem, das man mit einer Turingmaschine nicht lösen kann, gilt auch allgemeinhin als unlösbar.