Turingmaschine
Eine Turingmaschine ist ein von Alan Turing 1936 eingeführtes mathematisches Konstrukt, um eine Klasse von berechenbaren Funktionen zu bilden.
Eine Turing-Maschine besitzt ein lineares, unendliches Band, das in einzelne Felder eingeteilt ist.
Jedes Feld enthält genau ein Zeichen eines vorgegebenes Bandalphabets B, in dem ein Zeichen, das sog. Leerzeichen z, das für das leere Feld steht, ausgezeichnet ist. Es existiert ein Schreib- / Lesekopf, mit dem das Zeichen eines Feldes gelesen bzw. geschrieben werden kann. Die Maschine ist ein endlicher Automat mit der Zustandsmenge Z und dem Anfangszustand z0 aus dieser Zustandsmenge, sowie einer Teilmenge Z' von Z, die Menge der akzeptierenden Zustände. Weiterhin beinhaltet eine Turingmaschine das Arbeitsalphabet B, die Menge der Zeichen, die die TM erkennt. Alsdann gibt es eine Abbildungsvorschrift delta:ZxB -> ZxBx(-1,0,1), die für jedes Paar aus gelesenem Zeichen und aktuellem Zustand bestimmt, welches Zeichen auf das Band geschrieben werden soll, in welchen Zustand die Maschine übergehen soll und ob sich das Band nach rechts (1) oder links (-1) bewegen soll bzw. ob es halten (0) soll und damit "fertig!" signalisieren soll.
Die Turing-Maschine arbeitet also wie folgt: sie liest ein Zeichen vom Band. In Abhängigkeit vom gelesenen Zeichen und dem Zustand, in dem sie sich gerade befindet, schreibt sie ein Zeichen auf das Band, ändert ihren internen Zustand und bewegt den Schreib- / Lesekopf in die vorgegebene Richtung.
Die Menge turing-berechenbaren Funktionen ist die Menge aller Funktionen, die sich mit einer Turing-Maschine berechnen lassen (die Turing-Maschine muss die Aktion (H) ausführen!). Es gibt noch andere Verfahren, über die man Berechenbarkeit von Funktionen definieren kann, z.B. über rekursive Funktionen.
Es macht übrigens keinen Unterschied, ob eine Turing-Maschine eine oder mehrere Bänder verwendet. Auch das Bandalphabet kann beliebig groß sein, solange neben dem Leerzeichen ein weiteres Zeichen enthalten ist, ist eine Turing-Maschine zur allgemeinen Turing-Maschine gleichmächtig.
Ein beliebtes Problem ist der Fleissige Biber: man finde die Turing-Maschine, die mit einer bestimmten Anzahl von Zuständen die maximale Anzahl von "1"-Symbolen auf das Band schreibt und dann anhält. Bereits für nur 5 Zustände ist der "beste" Fleissige Biber noch nicht bekannt.