Mit Google fortfahren
Stell dir einen Papierstreifen mit vielen Kästchen vor. Du darfst immer nur das Kästchen unter deinem Stift ansehen. Mit festen Anweisungen kannst du trotzdem Schritt für Schritt eine Aufgabe lösen.
- Du kennst die Bauteile einer Turingmaschine.
- Du kannst einfache Regeln auf einem Band verfolgen.
- Du unterscheidest Anhalten, Akzeptieren und Endlosschleifen.
- Du verstehst die Bedeutung für die theoretische Informatik.
Die Grundidee
Die theoretische Informatik untersucht mit vereinfachten Modellen, was Computer grundsätzlich können und nicht können. Ein Algorithmus ist eine eindeutige Folge von Schritten zum Lösen einer Aufgabe.
Eine Turingmaschine ist ein gedankliches Modell eines sehr einfachen Computers. Sie folgt einem Algorithmus. Dabei bearbeitet sie nacheinander Zeichen auf einem langen Band.
Ein Zeichen ist ein Symbol, das die Maschine lesen oder schreiben kann, zum Beispiel 0, 1 oder ein Leerzeichen.
Eine Anweisung lautet: Lies eine 1, schreibe eine 0 und gehe ein Feld nach rechts.
Die Maschine muss nicht wissen, wofür die Zeichen stehen. Sie führt nur genau diese Anweisung aus.
Eine Turingmaschine ist keine echte Hardware. Sie ist ein Modell, mit dem man Programme und ihre Möglichkeiten untersuchen kann.
Interaktive Quizfrage wird geladen ...
Band, Kopf und Start
Das Band ist eine lange Reihe von Feldern. Jedes Feld enthält genau ein Zeichen. Die Eingabe steht zu Beginn auf einigen Feldern, die übrigen Felder sind leer.
Ein Lese Schreib Kopf zeigt auf das Feld, an dem die Maschine gerade arbeitet. Er kann das Zeichen dort lesen, ein Zeichen schreiben und anschließend ein Feld nach links oder rechts gehen.
Ein Zustand bezeichnet den aktuellen Arbeitsschritt der Maschine, etwa Prüfe oder Fertig. Der Startzustand ist der festgelegte Zustand, in dem jede Berechnung beginnt.
Ein Blank ist ein besonderes Leerzeichen auf dem Band. Es zeigt, dass ein Feld keine Eingabe enthält.
Auf dem Band steht 1 | 1 | 0 | Blank. Der Kopf steht auf der ersten 1.
Er liest zuerst die 1. Nach einer passenden Regel kann er sie verändern und auf das nächste Feld gehen.
Interaktive Lernkarten wird geladen ...
Interaktiver Lückentext wird geladen ...
Regeln für jeden Schritt
Eine Übergangsregel legt fest, was die Maschine in einer bestimmten Situation tun soll. Die Situation besteht aus dem aktuellen Zustand und dem Zeichen unter dem Kopf.
Die Regel bestimmt dann drei Dinge: welches Zeichen geschrieben wird, wohin der Kopf geht und welcher Zustand als Nächstes folgt. Eine deterministische Turingmaschine hat für jede Situation höchstens eine passende Regel. Deshalb ist ihr nächster Schritt eindeutig.
Die Regel lautet:
Im Zustand Prüfe bei einer 1: Schreibe 0, gehe nach rechts und bleibe in Prüfe.
Die Maschine ersetzt die gelesene 1 durch 0. Danach bewegt sie den Kopf ein Feld nach rechts. Sie arbeitet weiter im Zustand Prüfe.
Für Bewegungen nutzt man oft Abkürzungen: L bedeutet links und R bedeutet rechts. Manche Varianten erlauben auch Stillstehen.
Eine Übergangsregel schaut immer auf zwei Informationen: Zustand und Zeichen unter dem Kopf.
Interaktive Quizfrage wird geladen ...
Eine Maschine prüft Einsen
Nun folgt eine vollständige kleine Maschine. Sie soll erkennen, ob eine Eingabe nur aus Einsen besteht, zum Beispiel 111. Eine Eingabe wie 101 soll sie nicht akzeptieren.
Ein Endzustand ist ein Zustand, der das Ende einer Berechnung markiert. Ein akzeptierender Endzustand bedeutet: Die Eingabe erfüllt die gesuchte Bedingung.
Die Maschine hat die Zustände Prüfe und Ja. Ja ist ihr akzeptierender Endzustand. Ihre Regeln sind:
- Im Zustand Prüfe bei einer 1: Gehe nach rechts und bleibe in Prüfe.
- Im Zustand Prüfe bei einem Blank: Wechsle zu Ja.
- Bei einer 0 gibt es keine passende Regel.
Eingabe: 111
- Der Kopf liest die erste 1 und geht nach rechts.
- Er liest die zweite 1 und geht nach rechts.
- Er liest die dritte 1 und geht nach rechts.
- Er liest das Blank und wechselt in den Zustand Ja.
Die Maschine hält im akzeptierenden Endzustand. Deshalb akzeptiert sie die Eingabe.
Eingabe: 101
- Die erste 1 ist erlaubt. Der Kopf geht nach rechts.
- Danach liest der Kopf eine 0.
- Für diese Situation gibt es keine Regel.
Die Maschine hält nun, erreicht aber nicht den Zustand Ja. Deshalb akzeptiert sie 101 nicht.
Eine Eingabe wird nur akzeptiert, wenn die Maschine in einem akzeptierenden Endzustand anhält.
Interaktive Quizfrage wird geladen ...
Anhalten und endlos laufen
Eine Berechnung ist die Folge aller Schritte, die eine Turingmaschine ausführt. Eine Konfiguration ist eine Momentaufnahme: Sie enthält den Zustand, den Bandinhalt und die Position des Kopfes.
Eine Maschine hält, wenn keine Übergangsregel mehr anwendbar ist oder wenn sie einen vorgesehenen Haltzustand erreicht. Welche Schreibweise dafür genutzt wird, hängt von der genauen Modellvariante ab.
Eine Endlosschleife entsteht, wenn die Maschine immer weitere Schritte ausführt und nie hält. Dann gibt es kein fertiges Ergebnis.
Eine Maschine hat nur diese Regel:
Bei einem Blank: Gehe nach rechts und bleibe im selben Zustand.
Beginnt sie auf einem leeren Feld, liest sie immer wieder ein Blank. Sie geht endlos nach rechts und hält nicht an.
Interaktiver Lückentext wird geladen ...
Warum Turingmaschinen wichtig sind
Alan Turing beschrieb dieses Modell 1936, lange vor modernen Computern. Heute programmiert man damit nicht direkt Webseiten oder Spiele. Es hilft aber beim Nachdenken über die Grenzen von Programmen.
Berechenbarkeit bedeutet: Für jede erlaubte Eingabe gibt es eine eindeutige Anleitung, die nach endlich vielen Schritten ein Ergebnis liefert. Eine Aufgabe ist also nicht schon deshalb berechenbar, weil es Regeln gibt. Die Regeln müssen für alle erlaubten Eingaben zu einem Ergebnis führen.
Mit Turingmaschinen kann man außerdem untersuchen, wie viele Schritte oder wie viel Speicher eine Aufgabe benötigt. Besonders wichtig ist auch die Erkenntnis: Es gibt Fragen über Programme, die kein allgemeines Verfahren für alle möglichen Programme beantworten kann.
Die Turingmaschine klärt nicht, wie bequem oder schnell ein Computer arbeitet. Sie hilft zu verstehen, was Algorithmen prinzipiell leisten können.
Interaktive Quizfrage wird geladen ...
Zusammenfassung
Eine Turingmaschine ist ein einfaches Computermodell. Sie arbeitet auf einem Band mit einem Lese Schreib Kopf, Zuständen und Übergangsregeln. In jedem Schritt liest sie ein Zeichen, kann es verändern, bewegt den Kopf und wechselt den Zustand.
Sie kann eine Eingabe akzeptieren, ohne Akzeptanz anhalten oder endlos weiterlaufen. Deshalb ist sie ein wichtiges Werkzeug, um Algorithmen, Berechenbarkeit und die Grenzen von Computern zu verstehen.