Turingmaschine als Akzeptor

Einleitungstext für den Grundkurs

Im Baumarkt gibt es einen Automaten, der Schrauben und die passenden Anzahl Muttern eintütet. Zuerst wird die gewünschte Anzahl der Schrauben mit Mutter erfasst, dann die Schrauben und anschließend die Muttern in die Tüte gegeben. In eine Sprache übersetzt also: L = {Schraubeⁿ Mutterⁿ | n > 0}. Können wir einen Akzeptor konstruieren, der diese Sprache erkennt und akzeptiert?

Ansatz: Für n ≤ 3 liefert der Graph des Akzeptors (ohne Zustandsübergänge in einen Fehlzustand) eine Lösung:

Eine Erweiterung für größere n scheint auf den ersten Blick problemlos möglich, man muss nur neue Zustände einführen. Im allgemeinen Fall würde der Automat aber unendlich viele Zustände besitzen müssen. Dies widerspricht der Definition des Akzeptors. Diese Sprache kann also nicht von einem Akzeptor erkannt werden. 

Einleitungstext für den Leistungskurs

Unser Baumarkt erweitert sein Leistungsspektrum. Er bietet nun auch Schrauben, Unterlegscheiben und Muttern über den Automaten an (wow!). Die nachfolgende Generation soll zusätzlich auch Sprengringe (was das wohl ist) integrieren. In eine Sprache übersetzt also: L1 = {Schraubeⁿ Unterlegscheibeⁿ Mutterⁿ | n > 0} und L2 = {Schraubeⁿ Unterlegscheibeⁿ Sprengringⁿ Mutterⁿ | n > 0}. Können wir einen Kellerautomat konstruieren, der diese Sprache erkennt und akzeptiert?

Um es kurz zu machen: es wird uns nicht gelingen. Der Kellerautomat kann zwei Mengen vergleichen, versagt aber bei drei Mengen.

Mit der Turingmaschine liegt jedoch ein Automatenmodell vor, welches unsere Probleme lösen kann. Die Änderungen im Vergleich zum Akzeptor sind

• das Band wird beschreibbar und
• der Lese-/Schreibkopf ist beidseitig bewegbar.

Alan Turing entwickelte das mathematische Konzept einer universellen Maschine und stellt dies 1936 in der Arbeit "On Computable Numbers, with an Application to the 'Entscheidungsproblem'" vor. Dieser Beitrag gilt als die Geburtsurkunde der Wissenschaft Informatik. Turing selbst war entscheidend in weitere Projekte eingebunden, die heute der Informatik zugeordnet werden. Eine genaue Beschäftigung mit dem Leben und Wirken Turings erfolgt im Unterricht.  

Bildquelle: gemeinfrei von WikiCommons: https://commons.wikimedia.org/w/index.php?title=File:Alan_Turing_az_1930-as_%C3%A9vekben.jpg&oldid=450320260

Aufbau eines Funktionsmodells

Arbeitsweise

• SOLANGE ein Zustandsübergang möglich ist:
  • Lies mithilfe des Lesekopfs das Zeichen aus der aktuellen Zelle des Eingabebands.
  • Schreibe in Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen Automat ein Zeichen auf das Band, führe eine Lese-/Schreibkopfoperation (keine, eine Bewegung nach links/rechts) durch und wechsle dann in einen Folgezustand.
• Falls der aktuelle Zustand ein Endzustand ist, dann aktiviere die Akzeptanzanzeige.

Definition der Turingmaschine

Eine Turingmaschine TM = (X, Z, Γ, δ, z₀, $, Z_E) ist ein endlicher Automat ohne Ausgabe. Dabei gilt:

• X ... Eingabealphabet (nichtleere, endliche Menge)
• Z ... Zustandsmenge (nichtleere, endliche Menge)
• Γ ... Bandalphabet (nichtleere, endliche Menge)
• δ ... Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) höchstens eine Ausgabe, eine Kopfbewegung (L, N, R) und einen Folgezustand zuordnet
• z₀ ∈ Z ist der Anfangszustand
• $ ... Bandvorbelegungszeichen
• Z_E ⊆ Z ... Endzustandsmenge (nichtleere, endliche Menge)

Beispiel für das Grundkurs-Problem: TM zur Erkennung der Sprache L(A) = {SchraubeⁿMutterⁿ | n > 0}

TM = (X, Z, Γ, δ, z₀, $, Z_E) mit

• • X ={Schraube, Mutter}
  • Z = {q₀, q₁, q₂, q₃, q₄, q₅}
  • Γ ={$, Schraube, Mutter}
  • q₀ ∈ Z ist der Anfangszustand
  • Z_E = {q₅}
  • δ als Tabelle 
    
    oder als Graph
    

Beispiel für das Leistungskurs-Problem: TM zur Erkennung der Sprache L(A) = {SchraubeⁿUnterlegscheibeⁿMutterⁿ | n > 0}

TM = (X, Z, Γ, δ, z₀, $, ZE) mit

• X ={Schraube, Unterlegscheibe, Mutter}
• Z = {q₀, ..., q₈}
• Γ ={$, Schraube, Unterlegscheibe, Mutter}
• q₀ ∈ Z ist der Anfangszustand
• Z_E = {q₈}
• δ als Tabelle 
  
  oder als Graph