Zum Inhalt springen

Turingmaschine

Aus FLBK-Wiki
Version vom 11. November 2026, 22:08 Uhr von Flbkwikiadmin (Diskussion | Beiträge)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Die Turingmaschine ist ein sehr einfaches Modell eines Rechners und kann trotzdem alles berechnen, was ein Computer berechnen kann. An ihr lässt sich auch zeigen, was kein Computer leisten kann.

Definition

Eine Turingmaschine ist ein 7-Tupel [math]\displaystyle{ M = (Q; \Sigma; \Gamma; \delta; q_0; \square; F) }[/math]:

  • [math]\displaystyle{ Q }[/math] ist die endliche, nicht leere Zustandsmenge.
  • [math]\displaystyle{ \Sigma }[/math] ist das Eingabealphabet.
  • [math]\displaystyle{ \Gamma }[/math] ist das Bandalphabet mit [math]\displaystyle{ \Sigma \subset \Gamma }[/math].
  • [math]\displaystyle{ \delta: Q \times \Gamma \to Q \times \Gamma \times \{L; R\} }[/math] ist die Übergangsfunktion. Sie muss nicht für jedes Paar aus Zustand und Zeichen einen Wert haben.
  • [math]\displaystyle{ q_0 \in Q }[/math] ist der Startzustand.
  • [math]\displaystyle{ \square \in \Gamma \setminus \Sigma }[/math] ist das Leerzeichen.
  • [math]\displaystyle{ F \subseteq Q }[/math] ist die Menge der Endzustände.

Die Maschine arbeitet auf einem Band, das in beide Richtungen unbegrenzt ist. Jedes Feld des Bandes trägt ein Zeichen aus [math]\displaystyle{ \Gamma }[/math]. Ein Lese-Schreib-Kopf steht auf genau einem Feld. Anders als ein endlicher Automat kann die Turingmaschine ihre Eingabe verändern, und anders als ein Kellerautomat erreicht sie jede Stelle ihres Speichers. Jeder endliche Automat und jeder Kellerautomat lässt sich durch eine Turingmaschine nachbilden. Die Sprachen, die Turingmaschinen erkennen, bilden Typ 0 der Chomsky-Hierarchie.

Arbeitsweise

Zu Beginn steht die Eingabe auf dem Band, alle übrigen Felder tragen [math]\displaystyle{ \square }[/math]. Die Maschine startet in [math]\displaystyle{ q_0 }[/math], der Kopf steht auf dem ersten Zeichen der Eingabe.

In jedem Schritt liest der Kopf ein Feld. Die Übergangsfunktion legt dann drei Dinge fest: das Zeichen, das auf das Feld geschrieben wird, die Bewegung des Kopfes um ein Feld nach links ([math]\displaystyle{ L }[/math]) oder rechts ([math]\displaystyle{ R }[/math]) und den Folgezustand.

Die Maschine hält, wenn sie einen Endzustand erreicht oder wenn für den Zustand und das gelesene Zeichen kein Übergang festgelegt ist. Hält sie in einem Endzustand, hat sie die Eingabe akzeptiert, und das Ergebnis der Berechnung steht auf dem Band. Hält sie in einem anderen Zustand, hat sie die Eingabe abgelehnt. So beantwortet eine Turingmaschine eine Frage mit ja (akzeptiert) oder nein (abgelehnt). Eine Turingmaschine muss nicht halten: Sie kann auch endlos weiterlaufen.

Entscheidbarkeit

Die These von Church und Turing besagt: Was überhaupt berechenbar ist, kann eine Turingmaschine berechnen. Berechenbar heißt eine Aufgabe, wenn es ein Verfahren gibt, das sie in endlich vielen, eindeutig festgelegten Schritten löst. Die Aussage heißt These und nicht Satz, weil sie sich nicht beweisen lässt: Was als Verfahren gilt, ist nicht mathematisch festgelegt. Bisher wurde aber kein Verfahren gefunden, das sich nicht durch eine Turingmaschine nachbilden lässt. Was eine Turingmaschine nicht kann, kann deshalb auch kein Programm in Java oder einer anderen Programmiersprache.

Ein Problem ist hier eine Frage, die für jede Eingabe mit ja oder nein zu beantworten ist. Ein Problem heißt entscheidbar, wenn es eine Turingmaschine gibt, die bei jeder Eingabe nach endlich vielen Schritten hält und die richtige Antwort gibt. Gibt es keine solche Maschine, heißt das Problem unentscheidbar.

Unentscheidbar ist das Halteproblem. Es fragt, ob ein Programm bei einer Eingabe irgendwann hält. Die Frage ist sinnvoll, weil ein Programm selbst ein Text ist und deshalb als Eingabe eines anderen Programms dienen kann, so wie ein Quelltext die Eingabe eines Compilers ist.

Beweisidee: Angenommen, es gäbe ein Programm [math]\displaystyle{ H }[/math], das für jedes Programm [math]\displaystyle{ p }[/math] und jede Eingabe [math]\displaystyle{ e }[/math] entscheidet, ob [math]\displaystyle{ p }[/math] bei [math]\displaystyle{ e }[/math] hält. Dann ließe sich ein Programm [math]\displaystyle{ D }[/math] bauen. [math]\displaystyle{ D }[/math] erhält ein Programm [math]\displaystyle{ p }[/math] und fragt [math]\displaystyle{ H }[/math], ob [math]\displaystyle{ p }[/math] bei der Eingabe [math]\displaystyle{ p }[/math] hält. Antwortet [math]\displaystyle{ H }[/math] mit „hält“, läuft [math]\displaystyle{ D }[/math] endlos. Antwortet [math]\displaystyle{ H }[/math] mit „hält nicht“, hält [math]\displaystyle{ D }[/math].

Wird [math]\displaystyle{ D }[/math] auf sich selbst angewendet, widerspricht jede Antwort von [math]\displaystyle{ H }[/math]. Sagt [math]\displaystyle{ H }[/math], dass [math]\displaystyle{ D }[/math] bei der Eingabe [math]\displaystyle{ D }[/math] hält, läuft [math]\displaystyle{ D }[/math] endlos. Sagt [math]\displaystyle{ H }[/math], dass [math]\displaystyle{ D }[/math] nicht hält, hält [math]\displaystyle{ D }[/math]. Also kann es [math]\displaystyle{ H }[/math] nicht geben.

Unentscheidbar bedeutet nicht „schwierig“ oder „langsam“. Es bedeutet: Kein Verfahren beantwortet die Frage für alle Eingaben richtig. Für einzelne Programme lässt sie sich oft beantworten. Eine Folge für die Praxis: Kein Werkzeug entscheidet für jedes Programm richtig, ob es hält. Tests und Analysen senken das Risiko einer Endlosschleife, ersetzen aber keinen vollständigen Nachweis.

Beispiele

Bits invertieren

Die Turingmaschine ersetzt jede [math]\displaystyle{ 0 }[/math] durch [math]\displaystyle{ 1 }[/math] und jede [math]\displaystyle{ 1 }[/math] durch [math]\displaystyle{ 0 }[/math]. Sie hat die Zustände [math]\displaystyle{ q_0 }[/math] (Startzustand) und [math]\displaystyle{ q_1 }[/math] (Endzustand), das Eingabealphabet [math]\displaystyle{ \Sigma = \{0; 1\} }[/math] und das Bandalphabet [math]\displaystyle{ \Gamma = \{0; 1; \square\} }[/math]. Das Zeichen [math]\displaystyle{ \square }[/math] steht für das Leerzeichen.

Zustand liest schreibt bewegt Folgezustand
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ 0 }[/math] [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_0 }[/math]
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ 0 }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_0 }[/math]
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ \square }[/math] [math]\displaystyle{ \square }[/math] [math]\displaystyle{ L }[/math] [math]\displaystyle{ q_1 }[/math]
Band, Zustand und Kopfposition beim Lauf für die Eingabe 10

Lauf für die Eingabe [math]\displaystyle{ 10 }[/math]:

  1. [math]\displaystyle{ q_0 }[/math] liest [math]\displaystyle{ 1 }[/math], schreibt [math]\displaystyle{ 0 }[/math] und geht nach rechts.
  2. [math]\displaystyle{ q_0 }[/math] liest [math]\displaystyle{ 0 }[/math], schreibt [math]\displaystyle{ 1 }[/math] und geht nach rechts.
  3. [math]\displaystyle{ q_0 }[/math] liest [math]\displaystyle{ \square }[/math], schreibt [math]\displaystyle{ \square }[/math] und geht nach links in [math]\displaystyle{ q_1 }[/math]. [math]\displaystyle{ q_1 }[/math] ist ein Endzustand, die Maschine hält.

Das Ergebnis auf dem Band ist [math]\displaystyle{ 01 }[/math].

Paritätsbit anhängen

Band, Zustand und Kopfposition beim Lauf für die Eingabe 101

Die Turingmaschine hängt an eine Folge von Bits ein Prüfbit an, das Paritätsbit: [math]\displaystyle{ 0 }[/math] bei einer geraden, [math]\displaystyle{ 1 }[/math] bei einer ungeraden Anzahl Einsen. Die Zustände merken sich, ob bisher gerade viele ([math]\displaystyle{ q_0 }[/math]) oder ungerade viele Einsen ([math]\displaystyle{ q_1 }[/math]) gelesen wurden. [math]\displaystyle{ q_2 }[/math] ist der Endzustand. Das Eingabealphabet ist [math]\displaystyle{ \Sigma = \{0; 1\} }[/math], das Bandalphabet [math]\displaystyle{ \Gamma = \{0; 1; \square\} }[/math]. Der Kopf bewegt sich in jedem Schritt nach rechts.

Zustand liest schreibt bewegt Folgezustand
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ 0 }[/math] [math]\displaystyle{ 0 }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_0 }[/math]
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_1 }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ 0 }[/math] [math]\displaystyle{ 0 }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_1 }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_0 }[/math]
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ \square }[/math] [math]\displaystyle{ 0 }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_2 }[/math]
[math]\displaystyle{ q_1 }[/math] [math]\displaystyle{ \square }[/math] [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_2 }[/math]

Lauf für die Eingabe [math]\displaystyle{ 101 }[/math]:

  1. [math]\displaystyle{ q_0 }[/math] liest [math]\displaystyle{ 1 }[/math], lässt die [math]\displaystyle{ 1 }[/math] stehen und wechselt nach [math]\displaystyle{ q_1 }[/math]: Bisher wurde eine ungerade Anzahl Einsen gelesen.
  2. [math]\displaystyle{ q_1 }[/math] liest [math]\displaystyle{ 0 }[/math], lässt sie stehen und bleibt in [math]\displaystyle{ q_1 }[/math].
  3. [math]\displaystyle{ q_1 }[/math] liest [math]\displaystyle{ 1 }[/math] und wechselt nach [math]\displaystyle{ q_0 }[/math]: Jetzt ist die Anzahl gerade.
  4. [math]\displaystyle{ q_0 }[/math] liest [math]\displaystyle{ \square }[/math]: Die Eingabe ist zu Ende. Die Maschine schreibt das Prüfbit [math]\displaystyle{ 0 }[/math] auf das leere Feld und wechselt in den Endzustand [math]\displaystyle{ q_2 }[/math].

Das Ergebnis auf dem Band ist [math]\displaystyle{ 1010 }[/math]. Anders als im ersten Beispiel beschreibt die Maschine ein Feld, das vorher leer war: Das Band ist ihr Arbeitsspeicher und nicht nur ihre Eingabe.

Eingabe ablehnen

Die Turingmaschine prüft, ob eine Folge von Bits nur aus Nullen besteht. Sie hat die Zustände [math]\displaystyle{ q_0 }[/math] (Startzustand) und [math]\displaystyle{ q_1 }[/math] (Endzustand), das Eingabealphabet [math]\displaystyle{ \Sigma = \{0; 1\} }[/math] und das Bandalphabet [math]\displaystyle{ \Gamma = \{0; 1; \square\} }[/math].

Zustand liest schreibt bewegt Folgezustand
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ 0 }[/math] [math]\displaystyle{ 0 }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_0 }[/math]
[math]\displaystyle{ q_0 }[/math] [math]\displaystyle{ \square }[/math] [math]\displaystyle{ \square }[/math] [math]\displaystyle{ R }[/math] [math]\displaystyle{ q_1 }[/math]

Für [math]\displaystyle{ q_0 }[/math] und das Zeichen [math]\displaystyle{ 1 }[/math] ist kein Übergang festgelegt.

  • Eingabe [math]\displaystyle{ 000 }[/math]: [math]\displaystyle{ q_0 }[/math] liest dreimal [math]\displaystyle{ 0 }[/math], lässt die Zeichen stehen und geht jeweils nach rechts. Dann liest [math]\displaystyle{ q_0 }[/math] das Leerzeichen [math]\displaystyle{ \square }[/math] und wechselt in den Endzustand [math]\displaystyle{ q_1 }[/math]. Die Maschine hält in einem Endzustand: Die Eingabe ist akzeptiert, die Antwort lautet ja.
  • Eingabe [math]\displaystyle{ 010 }[/math]: [math]\displaystyle{ q_0 }[/math] liest [math]\displaystyle{ 0 }[/math] und geht nach rechts. Dann liest [math]\displaystyle{ q_0 }[/math] die [math]\displaystyle{ 1 }[/math]. Dafür gibt es keinen Übergang, die Maschine hält in [math]\displaystyle{ q_0 }[/math]. Das ist kein Endzustand: Die Eingabe ist abgelehnt, die Antwort lautet nein.

Die Maschine hält bei jeder Eingabe nach endlich vielen Schritten und gibt die richtige Antwort. Die Frage „Besteht die Eingabe nur aus Nullen?“ ist damit entscheidbar.

Entscheidbare und unentscheidbare Fragen unterscheiden

Für drei Fragen wird geprüft, ob sie entscheidbar sind:

  • „Enthält ein Text die Zeichenfolge UML?“ Die Frage ist entscheidbar. Schon ein DEA wie der Spam-Filter liest den Text einmal von vorn nach hinten, hält nach dem letzten Zeichen und antwortet mit akzeptiert oder abgelehnt.
  • „Ist ein Klammerausdruck korrekt geklammert?“ Die Frage ist entscheidbar. Ein Kellerautomat liest den Ausdruck einmal und hält bei jeder Eingabe.
  • „Hält ein beliebiges Programm bei einer beliebigen Eingabe?“ Die Frage ist unentscheidbar, das ist das Halteproblem. Für einzelne Programme ist die Antwort trotzdem leicht: Ein Programm, das nur aus der Schleife while (true) { } besteht, hält nie. Ein Programm ohne Schleifen und ohne Methodenaufrufe hält immer. Es gibt aber kein Verfahren, das für jedes Programm die richtige Antwort findet.