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 endlichen 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. Mit einem Kellerspeicher lässt sich beispielsweise die Anzahl zweier aufeinanderfolgender Zeichengruppen vergleichen. Für den Vergleich drei aufeinanderfolgender Zeichengruppen reicht ein einzelner Kellerspeicher jedoch nicht aus.

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.

Dadurch kann die Turingmaschine bereits gelesene Informationen auf dem Band verändern und später erneut verwenden.

Alan Turing entwickelte das mathematische Konzept einer universellen Maschine und stellt dies 1936 in seiner Arbeit "On Computable Numbers, with an Application to the 'Entscheidungsproblem'" vor. Diese Arbeit zählt zu den grundlegenden Beiträgen der theoretischen 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

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 vom gelesenen Zeichen ein Zeichen auf das Band, bewege den Lese-/Schreibkopf gegebenenfalls nach links oder rechts und wechsle in einen Folgezustand.
• Falls der aktuelle Zustand ein Endzustand ist, dann aktiviere die Akzeptanzanzeige. 
• Hält die Maschine in einem Endzustand, wird das Eingabewort akzeptiert.

Definition der Turingmaschine

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

• X ... Eingabealphabet (nichtleere, endliche Menge)
• Z ... Zustandsmenge (nichtleere, endliche Menge)
• Γ ... Bandalphabet (nichtleere, endliche Menge) und X ⊆ Γ
• δ ... Überführungsfunktion, die in Abhängigkeit vom aktuellen Zustand und vom gelesenen Bandzeichen festlegt, welches Zeichen auf das Band geschrieben wird, wie sich der Lese-/Schreibkopf bewegt (L, N oder R) und in welchen Folgezustand die Maschine wechselt.
• z₀ ∈ Z ist der Anfangszustand
• $ ... Bandvorbelegungszeichen, kennzeichnet eine zunächst unbeschriebene Zelle.
• Z_E ⊆ Z ... Endzustandsmenge (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