Was sind Turingmaschinen ?

Eine Turingmaschine besteht aus einem Lese-/Schreibkopf, der mechanisch über ein unendlich langes Band hin- und her bewegt werden kann. Auf dem Band können Zeichen stehen. Alle erlaubten zeichen bilden das Alphabet.
Der Lese-/Schreibkopf kann jeweils das aktuelle Zeichen lesen und überschreiben. Zusätzlich kann er um einen Schritt nach links oder rechts bewegt werden.

Zu jedem Zeitpunkt befindet sich die Maschine in einem definierten Zustand. Ist die Maschine z. B. im Zustand "nach rechts laufen", so liest sie die aktuellen Zeichen ohne sie zu verändern und bewegt den Kopf um jeweils einen Schritt nach rechts, bis sie etwa auf ein leeres Feld trifft. In diesem Fall bewegt sie sich um einen Schritt nach links.

Die Steuerung des Kopfes übernimmt ein kleines Programm (endlicher Automat). Die Anweisungen bestehen in Textform aus einem 5er-Tupel:

 (Ausgangszustand;akt. Zeichen;neues Zeichen;Endzustand;Positionierung)
  "Wenn im Ausgangszustand ein bestimmtes Zeichen gelesen wird,
   dann wird ein (anderes) Zeichen zurückgeschrieben und ggf. der Kopf
   um einen Schritt nach links oder rechts bewegt.
   Das Programm wird in einem Folgezustand fortgesetzt (kann auch derselbe 
   Zustand wieder sein).