Turingmaskiner

Eine Turingmaschine ist ein abstraktes mathematisches Modell der Berechnung, das von Alan Turing im Jahr 1936 eingeführt wurde, um das Konzept der algorithmischen Berechenbarkeit zu untersuchen und das Entscheidungsproblem zu analysieren. Sie besteht aus einem endlichen Satz von Zuständen, einem unbegrenzten Band, das in Zellen unterteilt ist, einem Lese-Schreib-Kopf, der das Band lesen oder schreiben kann, und einer Übergangsfunktion, die auf dem aktuellen Zustand und dem gelesenen Symbol basiert und den nächsten Zustand, das zu schreibende Symbol sowie eine Bewegung des Kopfes (links oder rechts) bestimmt.

Formell wird eine Turingmaschine oft als 7-Tupel definiert: (Q, Σ, Γ, δ, q0, q_accept, q_reject). Q ist die endliche Zustandsmenge, Σ das Eingabealphabet, Γ das Bandalphabet (mit Σ ⊆ Γ und einem Leerzeichen als Blank), δ die Übergangsfunktion δ: Q × Γ → Q × Γ × {L, R}, q0 der Startzustand, q_accept ein Haltezustand für akzeptierende Berechnungen und q_reject ein Haltezustand für ablehnende Berechnungen. Eine deterministische Turingmaschine besitzt eine eindeutig definierte δ, es gibt auch nichtdeterministische Varianten. Erweiterte Modelle wie Mehrfachbänder-Turingmaschinen oder universelle Turingmaschinen ergänzen oder simulieren andere Maschinen, ohne die Menge der berechenbaren Funktionen zu erhöhen.

Die Turingmaschine bildet das Kernkonzept der Berechenbarkeitstheorie und ist eng mit der Church-Turing-These verbunden, nach der alle intuitiv berechenbaren Funktionen von einer Turingmaschine berechnet werden können. Sie dient zur Begründung von Entscheidungs- und Undekidierbarkeitsergebnissen, etwa des Halteproblems. In der Praxis dient das Modell als theoretische Grundlage für das Verständnis der Leistungsfähigkeit moderner Computer, die in ihrem Berechnungsumfang als Turing-äquivalent betrachtet werden.

---