3.2 Turing-Automaten und Regel-Sprachen

Um die Klasse der von Automaten akzeptierten Sprachen über die kontextfreien Sprachen hinaus zu erweitern, heben wir die beim Kellerautomaten angenommene Beschränkung des RAM-Speichers als Keller wieder auf und betrachten ein unendliches Speicherband, wo an beliebigen Stellen (Zellen) gelesen und geschrieben werden kann. Wir benutzen dazu das nach beiden Seiten offene Eingabeband. Um beliebige Stellen dieses Bandes zu erreichen, geben wir dem Automaten die Möglichkeit, neben dem Lese- und Schreibvorgang, ausgehend von einer Zelle die linke oder rechte Nachbarzelle aufzusuchen. Zusammen mit dem zu schreibenden Symbol wird diese Bewegungsmöglichkeit durch eine Ausgabereaktion des Automaten bestimmt. Wir folgen dem von Turing (1936) vorgeschlagenen Modell des Turing-Automaten und untersuchen die von diesem akzeptierte Sprachklasse.

Definition: Turing-Automat Eine Struktur T = ( X, Y, Z, h, z0, F, # ) heißt Turing-Automat , falls X, Y, Z nichtleere endliche Mengen, X  Y, Y  Z =  , #  Y \ X , z0 Z, F  Z und h eine Funktion aus Y  Z in die Potenzmenge über Y  Z  { r, l, o }. (Die im allgemeinen partielle Funktion h mit Tripelmengen als Funktionswerte kann auch als Relation über Y  Z  Y  Z  { r, l, o } aufgefaßt werden. r, l, o kennzeichnen die Bewegungsmöglichkeiten als Ausgabereaktion.) Bezeichnungen: X Eingabealphabet, Y Bandalphabet,   Z Zustandsmenge, F Endzustandsmenge,   z0 Anfangszustand, # Leerfeldsymbol (Blank),   h Überführungsfunktion.

Schematisch kann man einen Turing-Automaten wie folgt darstellen:
 

Bemerkung: Hinsichtlich der Realisierung des Speichers und seiner Nutzung sind

noch andere Modellvorstellungen entwickelt worden, z.B. mehrere Speicher mit verschiedenen Grundalphabeten, andere Adressierungs- bzw. Bewegungsmöglichkeiten, die im wesentlichen aber keine grundsätzliche Erweiterungen gegenüber dem obigen Modell darstellen.

Zu einer Konfiguration pzq werden Folgekonfigurationen p´z´q´ als Verhaltensreaktion des Automaten wie folgt definiert:

Wenn (y, z´, r)  h(x, z) mit q = xw , dann ist p´ = py und q´= w möglich.

Wenn (y, z´, l)  h(x, z) mit p = vx´, q = xw, dann ist p´ = v und q´ = x´yw möglich.

Wenn (y, z´, o)  h(x, z) mit q = xw , dann ist p´= p und q´= yw möglich.

Bei Bewegung	r	durch die Regel	zx  yz´ ,
bei	l	durch die Regel	zx  z´y ,
und bei	o	durch die Regel	x´zx  z´x´y für beliebige x´ Y.

Fassen wir diese Regeln zur Regelmenge RT zusammen, dann kann der Übergang von der Konfiguration pzq zu einer Folgekonfiguration p´z´q´ wie üblich mit pzq  p´z´q´ durch Regelanwendung beschrieben werden, wobei die Symbole # vor p bzw. hinter q nach Bedarf zu ergänzen sind.

Bezeichnet * wieder die reflexiv, transitive Hülle von  , dann ist die von dem Turing-Automaten akzeptierte Sprache durch die Wortmenge

L ( T ) = { q  q  X* und es existiert ein z_f F mit z₀q  * vz_fw }

Ein Wort q , als Anfangsbeschriftung des Speicherbandes, wird vom Turing-Automat genau dann akzeptiert, wenn die Konfigurationsfolge zu einem Endzustand führt. Das Eingabewort q muß dabei nicht notwendig vollständig gelesen werden. Die Akzeption sagt nichts darüber aus, nach wieviel Schritten ein Endzustand erreicht wird. Da h allgemein partiell ist, muß nicht zu jeder Konfiguration eine Folgekonfiguration definiert sein. In diesem Fall sagt man , daß der Turing-Automat hält. Wird ein Wort nicht akzeptiert, dann kann die Konfigurationsfolge unter Umständen unbeschränkt fortsetzbar sein, ohne daß ein Endzustand angenommen wird oder der Automat anhält.

Modellvarianten :

1. Turing-Automaten mit halbseitig unendlichem Speicher
   Da der Automat zu jedem Zeitpunkt nur einen endlichen Speicherbereich benutzt hat, kann bei notwendigen Bewegungen über das Speicherende vorher eine gegenläufige Verschiebung des benutzten Speicherbereiches vorgenommen werden. (Auffüllen mit Blanks.)

2. Mehrband-Turing-Automaten
   Mehrere Speicherbänder können zu einem Speicherband mit mehreren Spuren zusammengefaßt werden. Die Zellen des gemeinsamen Speicherbandes werden entsprechend mit Tupel von Symbolen beschriftet, die auf den gegebenen Speicherbänder stehen. Zur Festlegung der jeweils aktuell zu lesenden Zelle wird das dort vorhandene Symbol in der Beschriftung des gemeinsamen Speicherbandes auf der entsprechenden Spur durch einen Doppelgänger ersetzt. Diese Doppelgänger sind als neue Symbole in die Menge Y aufzunehmen. Sobald die jeweilige Zelle nicht mehr aktuell ist, wird an dieser Stelle auf der entsprechenden Spur wieder das Originalsymbol eingetragen.

Beide Varianten können daher auf das ursprüngliche Modell des Turing-Automaten zurückgeführt werden.

Definition: Deterministischer Turing-Automat Ein Turing-Automat T = ( X, Y, Z, h, z0, F, # ) heißt deterministisch , falls h eine allgemein partielle Funktion aus Y  Z in Y  Z  { r, l, o } ist, d.h.,  h ( y, z )   1 für alle y  Y und z  Z.

Beweisidee: O.B.d.A. kann von Turing-Automaten mit einem Speicherband und

jeweils höchstens zwei möglichen Folgekonfigurationen ausgegangen werden. Die bildbaren Konfigurationsfolgen können dann als Wörter über einem binären Alphabet codiert werden. Es wird jetzt ein Dreiband-Automat konstruiert, der im ersten Band das Eingabewort und im zweiten Band die Kodewörter für die Konfigurationsfolgen des nichtdeterministischen Automaten speichert. Nachdem ein Kodewort gespeichert wurde, wird die entsprechende Konfigurationsfolge auf dem dritten Band deterministisch ausgeführt.

 

Simulationen	Turingmaschine 1: Turingmaschine 2:[start]

Definition: Aufzählbare (berechenbare) Sprache Eine formale Sprache L heißt (rekursiv) aufzählbar , wenn es einen Turing-Automaten T mit L = L ( T ) gibt , d.h., der L akzeptiert.

Beispiel: Der Turing-Automat T=({0, 1}, {0, 1, N, E, #}, {z₀, z₁, z₂, z₃, z₄},h, z₀,{z₄}, #)

mit h nach Tabelle

kann in Analogie zu den anderen Automatenbegriffen auch durch den Graphen

festgelegt werden.
Der Automat T akzeptiert die Sprache L (T) = { 0ⁿ 1ⁿ n  1 }. Dabei bedeuten die Zustände:

 

z0	(Anfangszustand) ersetzt eine rechtsstehende 0 durch N mit Rechtsbewegung.
z1	sucht nach rechts die erste 1 und ersetzt diese durch E mit Linksbewegung.
z2	sucht nach links das erste N und geht danach mit Rechtsbewegung in den Zustand z0.
z3	sucht nach rechts das erste Blank und geht danach mit Rechtsbewegung in z4 über.
z4	(Endzustand) ist der akzeptierende Zustand .

3

Dieselbe Sprache wird durch den Zweiband-Automaten mit folgendem Graph akzeptiert.

Die Reaktionen auf den beiden Bändern sind jeweils in eckige Klammern gesetzt. Zunächst schreibt der Automat im Zustand z₀ die Nullen vor der ersten 1 vom ersten (Eingabe-)Band auf das zweite Band. Dann wird im Zustand z₁ geprüft, ob danach auf dem ersten Band soviele Einsen stehen wie auf dem zweiten Band Nullen. Nur dann geht der Automat in den akzeptierenden Zustand z₂ über.

Satz: Turing-Automaten und Typ-0 - Sprachen Eine formale Sprache L ist genau dann vom Typ-0 , wenn es einen sie akzeptierenden Turing-Automaten T mit L = L ( T ) gibt.

 

Beweis:

1. Konstruktion einer Typ-0 Grammatik G zum Turing-Automaten T mit
   L (T) = L (G):
   Sei T = (X, Y, Z, h, z₀, F, #) und S  Y  Z. Dann bilden wir M =Y  Z  {S} und das zu T gehörige Regelsystem R_T , so daß p  L (T) genau dann, wenn gilt z₀p  q₁z_fq₂ mit q_i Y*, z_f F mit Hilfe der Regeln aus R_T (bis auf Blanks).
   Wir bilden die Regelmenge R = R_T {z_f S, yS  S, Sy  S  z_f F, y Y}. Dann gilt p  L (T) genau dann, wenn z₀p  S mit den Regeln aus R. Die Grammatik G´ = (M, A, R´, S) mit A = X  Z  {#} und wo R´ aus R durch Umkehrung der Regeln entsteht erzeugt dann die Sprache L (G´) mit der Eigenschaft :
   { z₀p  p  L (T) } = L (G´)  { z₀ }A* . Aus G´ kann leicht die gesuchte Grammatik G mit L (G) = L (T) erzeugt werden.
2. Konstruktion eines Turing-Automaten T zur Typ-0 Grammatik G mit
   L(G)=L (T).

   Idee:Man bilde einen Zweiband-Automat , der auf dem ersten Band das

   Eingabewort p aufnimmt und damit auf dem zweiten Band die Ableitungen S  q der Grammatik G bildet. (Die Übergangsfunktion h des Turing-Automaten entspricht den Regeln der Grammatik, wie eingangs erläutert.) Danach werden Beschriftungen beider Bänder verglichen. Der Automat akzeptiert, wenn p = q .

Folgerungen:

1. Eine Sprache ist vom Typ-0 genau dann, wenn sie (rekursiv) aufzählbar ist.
2. Eine Sprache ist (rekursiv)aufzählbar genau dann, wenn sie von einem deterministischen Turing-Automaten (mit einem Band) akzeptiert wird

 

Definition: Entscheidbare Sprachen Eine formale Sprache L  X* heißt (rekursiv) entscheidbar, wenn es einen deterministischen Turing-Automaten T mit L = L (T) gibt, der für jede Eingabe p  X* hält .

 

Bemerkung: Für solche Sprachen ist durch T ein Entscheidungsverfahren gegeben,

mit dem für jedes Wort aus X* festgestellt werden kann, ob es zu L gehört oder nicht. Diese Entscheidung kann am Zustand, den T nach dem Anhalten einnimmt, abgelesen werden. In jedem Fall erreicht der Turing-Automat T eine Konfiguration, zu der keine Folgekonfiguration existiert.

 

Satz: Zusammenhang zwischen aufzählbaren und entscheidbaren Sprachen. Eine Sprache L  X* ist genau dann entscheidbar, wenn L und ihr Komplement X* \ L aufzählbar ist.

 

Beweisidee:

1. Nach Definition ist L  X* genau dann entscheidbar, wenn ihr Komplement X* \ L entscheidbar ist. Jede entscheidbare Sprache ist aber auch aufzählbar.
2. Wenn L und X* \ L aufzählbar sind, dann existieren Turing-Automaten T und T´ mit L (T) = L und L (T´) = X* \ L . Man bilde einen Turing-Automaten mit zwei Bändern, der auf dem ersten Band den Automaten T und auf dem zweiten Band den Automaten T´ simuliert bei dem gleichen Eingabewort
   p  X*. Die Zustände dieses Automaten sind die Zustandspaare der Automaten T und T´. Der Automat soll anhalten (keine Folgekonfiguration definiert), sobald bei einem der Automaten T oder T´ein Endzustand ereicht wird. Das Wort p wird akzeptiert, wenn der Automat auf Band eins anhält, d.h., wenn T anhält.

Beweisidee:

Jede endliche algebraische Struktur kann über einem zweielementigen Alphabet {0, 1} kodiert werden, d.h., man kann eine injektive Funktion  angeben, die zu jeder Struktur eindeutig eine Folge (Kodewort) über {0, 1} bestimmt, aus der umgekehrt auch die kodierte Struktur wieder ermittelt werden kann. Die Werte von  und  -1 sind effektiv zu konstruieren. Entsprechendes gilt für Tupel aus (endlichen) Wörtern und Strukturen.Sei  eine solche Kodierungs-funktion der Paare (p, T), wo p  X* und T Turing-Automat über X.
Wir führen die (Universal)-Sprache L_u = {  (p, T)  p  L (T) }  {0, 1}* ein. L_u ist (rekursiv) aufzählbar und wird durch einen Zweiband-Automaten T_u akzeptiert, der auf dem ersten Band zur Eingabe  (p, T) entsprechend ^-1 zunächst p und T bestimmt und danach auf dem zweiten Band den Automaten T bei der Eingabe p simuliert. T_u akzeptiert  (p, T), wenn p von T akzeptiert wird. T_u heißt Universal-Automat , da er beliebige T simuliert.
Andererseits ist die (Diagonal)-Sprache L_d = {  ´(T)  ´(T)  L (T) } 
{0, 1}* , wo  ´(T) Kodewort von T, nicht aufzählbar, denn sonst müßte es einen Turing-Automaten T_d mit L (T_d) = L_d geben, wofür  ´(T_d)  L_d =
L (T_d) genau dann, wenn  ´(T_d)  L (T_d) ist.
Wäre nun {0, 1}* \ L_u aufzählbar, dann könnten wir L_d dadurch aufzählen, daß wir durch einen Turing-Automaten für die Eingabe ´(T) das Kodewort ( ´(T), T) erzeugen und akzeptieren, wenn dieses Wort nicht zu L_u gehört. Wenn aber {0, 1}* \ L_u nicht aufzählbar ist, dann kann die durch T_u aufzählbare Sprache L_u auch nicht entscheidbar sein.

Folgerung:

Die aufzählbaren Sprachen sind nicht abgeschlossen gegen Komplementbildung.

Defintion: Turing-berechenbare Funktion Sei T ein deterministischer Zweiband-Automat mit dem Alphabet X1 für das erste (Eingabe)-Band und X2 für das zweite (Ausgabe)-Band. fT bezeichne die Funktion , die genau für diejenigen Wörter p über X1 definiert ist, für die T mit p als Beschriftung des Eingabebandes anhält, und der Funktionswert fT(p) als Beschriftung des Ausgabebandes entsteht. Eine Funktion f aus X1* nach X2* heißt (Turing)-berechenbar, wenn es einen deterministischen Turing-Automaten T mit fT = f gibt.

Eigenschaften:

1. Jede im intuitiven Sinne berechenbare Funktion ist Turing-berechenbar.
2. Es gibt Funktionen, die nicht Turing-berechenbar sind.

Definition: Turing-erzeugbare Sprache Sei T ein nichtdeterministischer Mehrband-Automat mit einem (Ausgabe)-Band, auf dem nur von links nach rechts geschrieben werden kann. Mit ERZ(T) bezeichnen wir die Menge aller Inschriften dieses Ausgabebandes ohne Blanks, die entstehen, wenn T angesetzt auf leere Bänder anhält. Eine Sprache L heißt Turing-erzeugbar, wenn es einen nichtdeterministischen Turing-Automaten T mit ERZ(T) = L gibt.

 

Eigenschaften:

1. Jede Turing-erzeugbare Sprache ist (rekursiv)aufzählbar und umgekehrt.
2. Wenn L aufzählbar, dann gibt es einen Turing-Automaten der jedes Wort von L genau einmal erzeugt.
3. L ist genau dann entscheidbar, wenn es einen Turing-Automaten gibt, der die Wörter von L in aufsteigender Länge und genau einmal erzeugt.

Definition: (rekursiv) reduzierbare Sprachen Eine Sprache L1  X1* heißt auf die Sprache L2  X2* (rekursiv) reduzierbar (L1 L2), wenn es eine überall auf X1* definierte Turing-berechenbare Funktion f nach X2* gibt, für die f(p)  L2 genau dann gilt, wenn p  L1.

Eigenschaften:

1. Die Relation  ist reflexiv und transitiv.
2. L₁  L₂ genau dann, wenn X₁* \ L₁  X₂* \ L₂.
3. Wenn L₁  L₂ gilt und L₂ ist aufzählbar, dann ist auch L₁ aufzählbar.
4. L ist genau dann aufzählbar, wenn L  Lu mit L_u (Universal)-Sprache.

 

Definition: Eigenschaften P aufzählbarer Sprachen sind Teilklassen der Klasse L0 der Typ-0 Sprachen, d.h., Prädikate über L0. Eine Eigenschaft P heißt nicht-trivial, wenn P mindestens eine und nicht alle Sprachen aus L0 umfaßt, d.h., es gilt:  P  L0.

Beweisidee:

L sei eine aufzählbare Sprache mit L = L (T) und P sei eine nicht-triviale Eigenschaft aufzählbarer Sprachen , die auf L aber nicht auf  zutrifft, d.h.,
L  P und  P. Eine solche Eigenschaft P existiert, da P entscheidbar genau dann, wenn (nicht P ) entscheidbar ist.
Zu einem Wort q über dem Eingabealphabet von T konstruieren wir einen Turing-Automaten T_q der bei einem Wort p als Beschriftung des (Eingabe)Bandes genau dann anhält , wenn der Automat T bei p und der Automat T_u bei q anhält, d.h., es gilt : L (T_q) = { p  p  L und q  L (T_u) = L_u }. Also ist L (T_q) = L , falls q  L_u und L (T_q) =  , falls q  L_u.
Das bedeutet : L (T_q)  P genau dann, wenn q  L_u.
Sei L_p = { ´(T)  ´(T) Kodewort des Turing-Automaten T und L(T)  P}. Wäre L_p entscheidbar, dann wäre auch entscheidbar, ob L(T_q)  P gilt oder nicht. Damit wäre aber im Widerspruch zu früher L_u entscheidbar. Also kann L_p nicht entscheidbar sein. Damit ist auch die nicht-triviale Eigenschaft P nicht entscheidbar.

Folgerung: Es ist nicht entscheidbar, ob eine beliebige (rekursiv) aufzählbare

(Typ-0) Sprache leer, bzw. endlich, bzw. regulär, bzw. kontextfrei, bzw. kontextabhängig, bzw. entscheidbar ist. (Nicht-triviale Eigenschaften)

Bemerkungen:

1. Folgende Eigenschaften (rekursiv) aufzählbarer Sprachen L sind nicht (rekursiv) aufzählbar: L =  ; L = X* ; L rekursiv-aufzählbar ; L nicht rekursiv-aufzählbar ; L regulär ; L \ L_u  .
2. Folgende Eigenschaften (rekursiv) aufzählbarer Sprachen sind (rekursiv) aufzählbar : L   ;  L   k > 0 ; p  L für ein vorgegebenes festes
   p X* ; L  L_u.
3. Es ist nicht entscheidbar, ob ein (beliebiger) Turing-Automat bei leerem Eingabeband (nur Blanks) hält. (Halteproblem: Verallgemeinerung des Satzes von Rice)