Theoretische Informatik

Turingmaschine

 aufwärts

Die Turing­maschine ist ein sehr einfaches abstraktes Modell eines Computers – das gleichwohl mächtig genug ist, alles zu berechnen, was berechenbar ist.

Benannt ist die Turing­maschine nach A.M. Turingzur Person, der sie 1936 erdacht hat [Tur 36].

Idee

Das Maschinen­modell der Turing­maschine ist in Bild 1 dargestellt. Die Turing­maschine hat ein Steuerwerk, in dem sich das Programm befindet. Die Turing­maschine kann mit einem Schreib-/Lesekopf auf ein Arbeitsband zugreifen, sie kann dabei Zeichen auf dem Arbeitsband lesen und Zeichen auf das Arbeitsband schreiben. Ferner kann sie den Schreib-/Lesekopf nach links oder rechts bewegen.

Das Arbeitsband ist in Felder unterteilt. Der Anfang des Arbeits­bandes ist mit dem Band­begrenzungs­zeichen $ gekenn­zeichnet; nach rechts ist das Arbeitsband unbeschränkt.

Zu Beginn der Verarbeitung steht am Anfang des Arbeits­bandes ein Eingabewort, die restlichen Felder des Arbeits­bandes enthalten das Leerzeichen Leerzeichen.

Bild 1: Turingmaschine mit Eingabewort x = x0 ... x5
Bild 1: Turingmaschine mit Eingabewort x = x0 ... x5

Definition

Formal lässt sich die Turing­maschine wie folgt darstellen:

Definition:  Eine Turing­maschine ist ein Tupel

M = (Z, E, A, d, q, F).

Hierbei ist

Z eine endliche, nichtleere Menge von Zuständen des Steuerwerks,
E das Eingabe­alphabet,
A das Arbeits­alphabet,  wobei E enthalten in A,
d die Übergangs­relation  d enthalten in Z × A × A' × Z;  hierbei ist A' = A vereinigt {L, R},
q Element Z    der Startzustand,
F enthalten in Z    die Menge der Endzustände

Das Arbeits­alphabet A enthält die speziellen Zeichen $ und Leerzeichen; diese kommen nicht im Eingabe­alphabet vor. Die Zeichen L, R kommen nicht als Alphabet­zeichen vor.

Arbeitsweise

Die Elemente der Übergangs­relation d sind 4-Tupel der Form (s, a, a', s'). Diese stellen mögliche Zustands­übergänge der Turing­maschine dar, mit folgender Bedeutung: Wenn die Turing­maschine im Zustand s ist und das Zeichen a auf dem Arbeitsband liest, so überschreibt sie es mit dem Zeichen a' und geht in den Folgezustand s' über. Das Zeichen a' kann auch eines der Symbole L oder R sein; in diesem Fall schreibt die Turing­maschine nicht, sondern bewegt den Schreib-/Lesekopf nach links (L) oder nach rechts (R).

Wenn für jedes Paar, bestehend aus Zustand s und Zeichen a, höchstens ein solcher Zustands­übergang definiert ist, arbeitet die Turing­maschine deterministisch.

Es kann auch sein, dass für einen Zustand s und ein Zeichen a kein Folgezustand definiert ist; in diesem Fall hält die Turing­maschine.

Die Turing­maschine wird im Startzustand q gestartet. Der Schreib-/Lesekopf befindet sich auf dem ersten Feld hinter dem Band­begrenzungs­zeichen $. Dort steht das Eingabewort w auf dem Arbeitsband (siehe Bild 1).

Die Turing­maschine liest das erste Zeichen des Eingabewort und führt von dort ausgehend die ent­sprechenden weiteren möglichen Zustands­übergänge durch. Dabei können zwei Situationen auftreten. Entweder kommt die Turing­maschine irgendwann zu einem Zustand, von dem aus mit dem gelesenen Zeichen kein weiterer Zustands­übergang definiert ist, d.h. die Turing­maschine hält, oder die Turing­maschine kommt nie zu einem solchen Zustand, d.h. sie läuft unendlich lange weiter.

Oder genauer ausgedrückt: Entweder gibt es eine Folge von Zustands­übergängen, beginnend beim Startzustand q und mit dem Eingabewort w auf dem Arbeitsband, die irgendwann abbricht, weil kein weiterer Zustands­übergang mehr möglich ist. Oder es gibt keine solche abbrechende Folge, d.h. alle Folgen von Zustands­übergängen sind unendlich lang.

Wenn es eine solche abbrechende Folge von Zustands­übergängen gibt und deren letzter erreichter Zustand in der Menge F der Endzustände liegt, so erkennt die Turing­maschine das Eingabewort w. Wenn jede solche abbrechende Folge von Zustands­übergängen in einem Nicht-Endzustand endet, so weist die Turing­maschine das Eingabewort w zurück. Wenn es nur unendlich lange Folgen von Zustands­übergängen gibt, so erkennt sie das Eingabewort nicht, weist es aber auch nicht zurück.

Im Gegensatz zum endlichen Automaten oder auch zum Stack­automaten ist es nicht erforderlich, dass das Eingabewort vollständig gelesen worden ist.

Definition:  Die Menge aller Wörter, die von einer Turing­maschine M erkannt werden, heißt die von M erkannte Sprache; sie wird mit L(M) bezeichnet:

L(M)  =  { w Element E*  |  w wird von M erkannt }

Turingtabelle

Die Übergangs­relation d wird in Form einer Tabelle, der Turing­tabelle, angegeben. Jedes Element (s, a, a', s') der Übergangs­relation ist eine Zeile in der Turing­tabelle, mit folgender Bedeutung: Wenn die Turing­maschine im Zustand s ist und das Zeichen a liest, so schreibt sie das Zeichen a' (bzw. führt die Aktion a' aus, wenn a' = L oder a' = R ist) und geht in den Zustand s' über.

Beispiel:  Die folgende Turing­tabelle repräsentiert die Übergangs­relation d einer Turing­maschine M = (Z, E, A, d, q, F), die alle Eingabe­wörter der Form an mit n Element natürliche Zahlen0 erkennt.

Die Zustands­menge der Turing­maschine ist Z = {0, 1}, das Eingabe­alphabet ist E = {a, b}, das Arbeits­alphabet ist A = {a, b, $, Leerzeichen}, der Startzustand ist q = 0, die Menge der Endzustände ist F = {1}.

Arbeitsband

$
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

saa's'
 0 aR0
 0   1*






Die erste Zeile der Turing­tabelle bedeutet: Wenn die Turing­maschine im Zustand 0 ist und das Zeichen a liest, so geht sie auf dem Arbeitsband um eine Position nach rechts und bleibt im Zustand 0. Die zweite Zeile bedeutet: Wenn die Turing­maschine im Zustand 0 ist und das Leerzeichen Leerzeichen liest, so überschreibt sie es mit dem Leerzeichen Leerzeichen und geht in den Zustand 1 über.

Die Turing­maschine startet im Zustand 0. Wenn auf dem Arbeitsband als Eingabewort eine Folge von a's steht, so liest die Turing­maschine diese a's und bleibt dabei im Zustand 0. Wenn das Eingabewort zu Ende ist, liest die Turing­maschine das Leerzeichen Leerzeichen und geht in den Zustand 1 über. Vom Zustand 1 aus sind keine weiteren Zustands­übergänge möglich, d.h. die Turing­maschine hält. Da der Zustand 1 der Endzustand ist, erkennt sie das Eingabewort. Es kann auch sein, dass gleich das erste gelesene Zeichen das Leerzeichen ist, d.h. die Turing­maschine erkennt auch das leere Eingabewort a0 = ε.

Ein Zustands­übergang für den Zustand 0 und das Zeichen b ist in der Turing­tabelle nicht definiert. Dies führt dazu, dass die Turing­maschine hält, wenn sie im Zustand 0 ist und das Zeichen b liest. Da der Zustand 0 nicht der Endzustand ist, weist sie das Eingabewort in diesem Fall zurück.

Die von der Turing­maschine erkannte Sprache ist somit

L(M)  =  { an  |  n Element natürliche Zahlen0 }.

Das Arbeitsband ist links durch das Band­begrenzungs­zeichen $ begrenzt. Die Turing­maschine darf diese Begrenzung nicht über­schreiten. Wenn sie also das Zeichen $ liest, darf sie nicht nach links gehen; sie darf das Zeichen $ auch nicht durch ein anderes Zeichen über­schreiben. D.h. für die Übergangs­relation d muss gelten

(s, $, a', s')  Element  d    folgt    a' = R  oder  a' = $

Beispiele

 

Erkennung der Sprache { anbn | n Element natürliche Zahlen }

Die folgende Turing­maschine erkennt die Sprache { anbn  |  n Element natürliche Zahlen }. Sie liest solange a's, bis sie das erste b findet. Dann pendelt sie zwischen den a's und b's hin und her und löscht abwechselnd ein b und ein a.

Zum Schluss, wenn die Turing­maschine an das Ende der Eingabe kommt und ein Leerzeichen liest, überprüft sie noch, ob noch ein überzähliges a vorhanden ist.

Der Zustand 4 ist Endzustand; ferner gibt es einen expliziten reject-Zustand, dieser ist durch ein - dargestellt.

Arbeitsband

$
 
 
 
 
 
 
 
 
 
 
 
 
Pfeil

Eingabewort

   

 

saa's'
 0 aR0
 0 bx1
 0   -
 1 xL1
 1 ax2
 1 $R-
 2 xR2
 2 bx1
 2 aR-
 2  L3
 3 xL3
 3 aR-
 3 $R4*

Aufgaben

Aufgabe 1:  Entwerfen Sie eine Turing­maschine , die alle Wörter der Form a2nbn mit n Element natürliche Zahlen erkennt.

Simulieren Sie die Turing­maschine mit dem Turing­maschinen-Simulator.

Aufgabe 2:  Entwerfen Sie eine Turing­maschine , die alle Wörter der Form a2n mit n Element natürliche Zahlen0 erkennt.

Simulieren Sie die Turing­maschine mit dem Turing­maschinen-Simulator.

Aufgabe 3:  Entwerfen Sie eine Turing­maschine, die alle aus a's und b's bestehenden Wörter erkennt, die korrekten Klammer­strukturen entsprechen, wobei a einer öffnenden und b einer schließenden Klammer entspricht. Die Turing­maschine soll also beispiels­weise aababbab akzeptieren, aber abbabaab zurückweisen.

Simulieren Sie die Turing­maschine mit dem Turing­maschinen-Simulator.

Literatur

[Sip 96]M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company (1996)
[Tur 36]A.M. Turing: On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings, London Mathematical Society, 230-265 (1936)
[Weg 99]I. Wegener: Theoretische Informatik -- eine algorithmische Einführung. 2. Auflage, Teubner (1999)

 

Weiter mit:   [Chomsky-Hierarchie der Automaten]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 05.09.2004   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik