Was ist die Turingmaschine?
Eine Turingmaschine ist ein theoretisches Gerät zur Untersuchung der Berechenbarkeit und Lösbarkeit von Problemen in der Informatik und Mathematik.
Sie besteht aus einem unendlich langen Band und einem Lese-/Schreibkopf.
Das Band ist in Zellen unterteilt, auf denen Symbole gespeichert werden können.
Der Lese-/Schreibkopf kann die Symbole lesen, ändern und löschen sowie sich auf dem Band bewegen.
Die Maschine arbeitet gemäß einer "Turing-Tabelle", die Regeln festlegt, basierend auf dem aktuellen Zustand und dem gelesenen Symbol.
Turingmaschinen können jedes grundsätzlich lösbare Problem bewältigen, vorausgesetzt es gibt ausreichend Zeit und Speicherplatz.
Wie genau funktioniert die Turingmaschine?
Lesen: Die Maschine liest das Symbol auf dem Band an der aktuellen Position des Lese-/Schreibkopfs.
Übergangsfunktion: Die Maschine hat Anweisungen, die ihr sagen, was sie basierend auf ihrem aktuellen Zustand und dem gelesenen Symbol tun soll. Diese Anweisungen beinhalten den neuen Zustand, das zu schreibende Symbol und die Bewegungsrichtung.
Schreiben: Die Maschine kann das gelesene Symbol durch ein anderes ersetzen oder unverändert lassen.
Bewegen: Die Maschine bewegt den Lese-/Schreibkopf um eine Position nach links oder rechts auf dem Band.
Neuer Zustand: Die Maschine wechselt in einen neuen Zustand gemäß den Anweisungen.
Wiederholung: Der Zyklus aus Lesen, Schreiben, Bewegen und Zustandswechsel wird wiederholt, bis ein spezieller "Halt"-Zustand erreicht wird oder theoretisch unendlich oft.
Wie sieht eine Turingtabelle aus?
Last changed2 years ago
