Berechnungen einer TM
Eingabe steht auf Band, pro Feld ein Symbol
SL-Kopf auf dem am weitesten links stehenden Eingabesymbol S
Zustand ist Anfangszustand
In Abhängigkeit von Zustand und gelesenem Symbol gibt ? an
• auf Band geschriebenes neues Symbol,
• Bewegungsrichtung (Links, Rechts, Nicht bewegen)
Maschine führt so lange Aktionen aus, bis Zustand aus E erreicht wird ?
Ausgabe steht nun auf Band
Eine Funktion heißt Turing-berechenbar, wenn es eine Turing-Maschine gibt, die sie (im genannten Sinn) berechnet.