Automaten

Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes mathematisches Modell.

• 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.