Turingmaschine: Unterschied zwischen den Versionen
Die Seite wurde neu angelegt: „Die Turingmaschine ist das einfachste Modell, das alles berechnen kann, was ein Computer berechnen kann. Sie zeigt auch, wo diese Grenzen liegen. ==Definition== Eine Turingmaschine ist ein 7-Tupel <math>M = (Q, \Sigma, \Gamma, \delta, q0, \square, F)</math>: * <math>Q</math> ist die endliche, nicht leere Zustandsmenge. * <math>\Sigma</math> ist das Eingabealphabet. * <math>\Gamma</math> ist das Bandalphabet mit <math>\Sigma \subset \Gamma</…“ |
Keine Bearbeitungszusammenfassung Markierung: Manuelle Zurücksetzung |
||
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
Die Turingmaschine ist | 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== | ==Definition== | ||
Eine Turingmaschine ist ein 7-Tupel <math>M = (Q | Eine '''Turingmaschine''' ist ein 7-Tupel <math>M = (Q; \Sigma; \Gamma; \delta; q_0; \square; F)</math>: | ||
* <math>Q</math> ist die endliche, nicht leere Zustandsmenge. | * <math>Q</math> ist die endliche, nicht leere Zustandsmenge. | ||
* <math>\Sigma</math> ist das [[Alphabet|Eingabealphabet]]. | * <math>\Sigma</math> ist das [[Alphabet|Eingabealphabet]]. | ||
* <math>\Gamma</math> ist das Bandalphabet mit <math>\Sigma \subset \Gamma</math>. | * <math>\Gamma</math> ist das Bandalphabet mit <math>\Sigma \subset \Gamma</math>. | ||
* <math>\delta: Q \times \Gamma \to Q \times \Gamma \times \{L | * <math>\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> | * <math>q_0 \in Q</math> ist der Startzustand. | ||
* <math>\square \in \Gamma \setminus \Sigma</math> ist das Leerzeichen. | * <math>\square \in \Gamma \setminus \Sigma</math> ist das Leerzeichen. | ||
* <math>F \subseteq Q</math> ist die Menge der Endzustände. | * <math>F \subseteq Q</math> ist die Menge der Endzustände. | ||
Die Maschine arbeitet auf einem | Die Maschine arbeitet auf einem Band, das in beide Richtungen unbegrenzt ist. Jedes Feld des Bandes trägt ein [[Zeichen]] aus <math>\Gamma</math>. Ein Lese-Schreib-Kopf steht auf genau einem Feld. Anders als ein [[Endlicher Automat|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== | ==Arbeitsweise== | ||
Zu Beginn steht die Eingabe auf dem Band, alle übrigen Felder tragen <math>\square</math>. Die Maschine startet in | Zu Beginn steht die Eingabe auf dem Band, alle übrigen Felder tragen <math>\square</math>. Die Maschine startet in <math>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>L</math>) oder rechts (<math>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== | ==Entscheidbarkeit== | ||
Die These von Church und Turing besagt: Was überhaupt berechenbar ist, kann eine Turingmaschine berechnen. Ein Problem heißt entscheidbar, wenn eine Turingmaschine bei jeder Eingabe hält und | 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 [[Compiler|Compilers]] ist. | |||
Beweisidee: Angenommen, es gäbe ein Programm <math>H</math>, das für jedes Programm <math>p</math> und jede Eingabe <math>e</math> entscheidet, ob <math>p</math> bei <math>e</math> hält. Dann ließe sich ein Programm <math>D</math> bauen. <math>D</math> erhält ein Programm <math>p</math> und fragt <math>H</math>, ob <math>p</math> bei der Eingabe <math>p</math> hält. Antwortet <math>H</math> mit „hält“, läuft <math>D</math> endlos. Antwortet <math>H</math> mit „hält nicht“, hält <math>D</math>. | |||
Wird D auf sich selbst angewendet, widerspricht jede Antwort von H. Sagt H, dass D bei der Eingabe D hält, läuft D endlos. Sagt H, dass D nicht hält, hält D. Also kann es H nicht geben. | Wird <math>D</math> auf sich selbst angewendet, widerspricht jede Antwort von <math>H</math>. Sagt <math>H</math>, dass <math>D</math> bei der Eingabe <math>D</math> hält, läuft <math>D</math> endlos. Sagt <math>H</math>, dass <math>D</math> nicht hält, hält <math>D</math>. Also kann es <math>H</math> nicht geben. | ||
Eine Folge: Kein Werkzeug | 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== | ==Beispiele== | ||
===Bits invertieren=== | ===Bits invertieren=== | ||
Die Turingmaschine ersetzt jede 0 durch 1 und jede 1 durch 0. Sie hat die Zustände | Die Turingmaschine ersetzt jede <math>0</math> durch <math>1</math> und jede <math>1</math> durch <math>0</math>. Sie hat die Zustände <math>q_0</math> (Startzustand) und <math>q_1</math> (Endzustand), das Eingabealphabet <math>\Sigma = \{0; 1\}</math> und das Bandalphabet <math>\Gamma = \{0; 1; \square\}</math>. Das Zeichen <math>\square</math> steht für das Leerzeichen. | ||
{| class="wikitable" style="text-align:center" | {| class="wikitable" style="text-align:center" | ||
! Zustand !! liest !! schreibt !! bewegt !! Folgezustand | ! Zustand !! liest !! schreibt !! bewegt !! Folgezustand | ||
|- | |- | ||
| | | <math>q_0</math> || <math>0</math> || <math>1</math> || <math>R</math> || <math>q_0</math> | ||
|- | |- | ||
| | | <math>q_0</math> || <math>1</math> || <math>0</math> || <math>R</math> || <math>q_0</math> | ||
|- | |- | ||
| | | <math>q_0</math> || <math>\square</math> || <math>\square</math> || <math>L</math> || <math>q_1</math> | ||
|} | |} | ||
[[Datei:Turingmaschine Bits invertieren.png|mini|Band, Zustand und Kopfposition beim Lauf für die Eingabe 10]] | [[Datei:Turingmaschine Bits invertieren.png|mini|Band, Zustand und Kopfposition beim Lauf für die Eingabe 10]] | ||
# | Lauf für die Eingabe <math>10</math>: | ||
# | |||
# | # <math>q_0</math> liest <math>1</math>, schreibt <math>0</math> und geht nach rechts. | ||
# <math>q_0</math> liest <math>0</math>, schreibt <math>1</math> und geht nach rechts. | |||
# <math>q_0</math> liest <math>\square</math>, schreibt <math>\square</math> und geht nach links in <math>q_1</math>. <math>q_1</math> ist ein Endzustand, die Maschine hält. | |||
Das Ergebnis auf dem Band ist <math>01</math>. | |||
===Paritätsbit anhängen=== | |||
[[Datei:Turingmaschine Paritätsbit anhängen.png|mini|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>0</math> bei einer geraden, <math>1</math> bei einer ungeraden Anzahl Einsen. Die Zustände merken sich, ob bisher gerade viele (<math>q_0</math>) oder ungerade viele Einsen (<math>q_1</math>) gelesen wurden. <math>q_2</math> ist der Endzustand. Das Eingabealphabet ist <math>\Sigma = \{0; 1\}</math>, das Bandalphabet <math>\Gamma = \{0; 1; \square\}</math>. Der Kopf bewegt sich in jedem Schritt nach rechts. | |||
{| class="wikitable" style="text-align:center" | |||
! Zustand !! liest !! schreibt !! bewegt !! Folgezustand | |||
|- | |||
| <math>q_0</math> || <math>0</math> || <math>0</math> || <math>R</math> || <math>q_0</math> | |||
|- | |||
| <math>q_0</math> || <math>1</math> || <math>1</math> || <math>R</math> || <math>q_1</math> | |||
|- | |||
| <math>q_1</math> || <math>0</math> || <math>0</math> || <math>R</math> || <math>q_1</math> | |||
|- | |||
| <math>q_1</math> || <math>1</math> || <math>1</math> || <math>R</math> || <math>q_0</math> | |||
|- | |||
| <math>q_0</math> || <math>\square</math> || <math>0</math> || <math>R</math> || <math>q_2</math> | |||
|- | |||
| <math>q_1</math> || <math>\square</math> || <math>1</math> || <math>R</math> || <math>q_2</math> | |||
|} | |||
Lauf für die Eingabe <math>101</math>: | |||
# <math>q_0</math> liest <math>1</math>, lässt die <math>1</math> stehen und wechselt nach <math>q_1</math>: Bisher wurde eine ungerade Anzahl Einsen gelesen. | |||
# <math>q_1</math> liest <math>0</math>, lässt sie stehen und bleibt in <math>q_1</math>. | |||
# <math>q_1</math> liest <math>1</math> und wechselt nach <math>q_0</math>: Jetzt ist die Anzahl gerade. | |||
# <math>q_0</math> liest <math>\square</math>: Die Eingabe ist zu Ende. Die Maschine schreibt das Prüfbit <math>0</math> auf das leere Feld und wechselt in den Endzustand <math>q_2</math>. | |||
Das Ergebnis auf dem Band ist <math>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>q_0</math> (Startzustand) und <math>q_1</math> (Endzustand), das Eingabealphabet <math>\Sigma = \{0; 1\}</math> und das Bandalphabet <math>\Gamma = \{0; 1; \square\}</math>. | |||
{| class="wikitable" style="text-align:center" | |||
! Zustand !! liest !! schreibt !! bewegt !! Folgezustand | |||
|- | |||
| <math>q_0</math> || <math>0</math> || <math>0</math> || <math>R</math> || <math>q_0</math> | |||
|- | |||
| <math>q_0</math> || <math>\square</math> || <math>\square</math> || <math>R</math> || <math>q_1</math> | |||
|} | |||
Für <math>q_0</math> und das Zeichen <math>1</math> ist kein Übergang festgelegt. | |||
* '''Eingabe <math>000</math>:''' <math>q_0</math> liest dreimal <math>0</math>, lässt die Zeichen stehen und geht jeweils nach rechts. Dann liest <math>q_0</math> das Leerzeichen <math>\square</math> und wechselt in den Endzustand <math>q_1</math>. Die Maschine hält in einem Endzustand: Die Eingabe ist akzeptiert, die Antwort lautet ja. | |||
* '''Eingabe <math>010</math>:''' <math>q_0</math> liest <math>0</math> und geht nach rechts. Dann liest <math>q_0</math> die <math>1</math>. Dafür gibt es keinen Übergang, die Maschine hält in <math>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 <code>UML</code>?“''' Die Frage ist entscheidbar. Schon ein [[Deterministischer endlicher Automat|DEA]] wie der [[Endlicher Automat#Spam-Filter als NEA und DEA gegenüberstellen|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 <code>while (true) { }</code> 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. | |||
[[Kategorie:Automaten]] | [[Kategorie:Automaten]] | ||
[[Kategorie:AHR I Informatik LK]] | [[Kategorie:AHR I Informatik LK]] | ||