Zurück

Formale Beschreibung der Turingmaschine

Die formale Beschreibung einer Turingmaschine lautet A = (Q, Σ, Γ, q₀, Δ, F).

Fahre mit dem Cursor über die einzelnen Bestandteile des Tupels. Zu jedem Element wird die entsprechende Bedeutung beschrieben, sodass du dich Schritt für Schritt über den Aufbau einer Turingmaschine informieren kannst.

A = ( Q, Σ, Γ, q₀, Δ, F ) Die endliche Zustandsmenge Q. Das endliche Eingabealphabet Σ. Das endliche Arbeitsalphabet Γ, für das gilt: Σ ⊆ Γ, # ∈ Γ\Σ. # ist das Blanksymbol, das Zeichen für ein leeres Feld. Der Startzustand q₀ ∈ Q. Die Übergangsrelation Δ ⊆ Q × Γ × Γ × {r, l, n} × Q. {r, l, n} gibt die Bewegung des Lese-/Schreibkopfes an: nach rechts (r), nach links (l) oder gar nicht (n). Die Endzustandsmenge F ⊆ Q. Bsp.: A = ({q₀,q₁,qₑ}, {1,2}, {1,2,#}, q₀, Δ, {qₑ}) mit Δ: {(q₀,#,2,r,q₀), (q₀,1,1,r,q₁), (q₁,1,1,r,q₁), (q₂,#,2,n,qₑ)} q₀ q₁ qₑ #, 2, r 1, 1, r 1, 1, r #, 2, n
Formale Beschreibung der Turingmaschine