Unterschied zwischen einer Turing-Maschine und einer Finite-State-Maschine?

27

Ich mache einen Vortrag über Turingmaschinen und wollte einige Hintergrundinformationen zu FSMs geben, bevor ich Turingmaschinen vorstelle. Das Problem ist, ich weiß wirklich nicht, was sich SEHR voneinander unterscheidet.

Ich weiß, dass es anders ist:

FSM hat sequentielle Zustände, abhängig von der entsprechenden Bedingung, die erfüllt ist, während Turing-Maschinen auf einem unendlichen "Band" mit einem Kopf arbeiten, der liest und schreibt.

Es gibt mehr Raum für Fehler in FSMs, da wir leicht auf einen nicht endenden Zustand fallen können, während es nicht so sehr für Turing-Maschinen ist, da wir zurückgehen und Dinge ändern können.

Abgesehen davon kenne ich nicht viel mehr Unterschiede, die Turing-Maschinen besser machen als FSMs.

Kannst du mir bitte helfen?

terminology turing-machines finite-automata machine-models Julio Garcia
quelle
2
Es ist nicht schwer, nach "FSM vs. Turing Machine" zu googeln! Das ist der spaßige Teil Ihrer eigenen Recherche. Der Hauptunterschied besteht darin, dass eine Turing-Maschine einen unendlichen "Speicher" hat, ein FSM jedoch nicht.
Dai
Ok, ich habe dort ein bisschen geschummelt>.> ;; Erwischt! Vielen Dank!
Julio Garcia
3
Das Argument über "Fehler" ist nicht korrekt. Versuchen Sie Wikipedia und Kursbücher. Sehen Sie, was ihre grundlegenden Unterschiede sind, welchen Zweck sie haben (z. B. wenn wir kein FSM über TM wählen können?) Und in welcher Beziehung sie zueinander stehen.
Parham
@ MahmoudAlimohamadi Ich meine, es gibt eine größere Chance für ein FSM, in einem nicht endenden Zustand zu landen.
Julio Garcia
@Dai: Es ist richtiger zu sagen , dass eine Turing - Maschine kann verwenden eine beliebig große Menge an Speicher. Die verwendete Menge ist niemals unendlich.
Reinierpost

Antworten:

24

Der Hauptunterschied zwischen der Funktionsweise von DFAs (Deterministic Finite Automaton) und TMs besteht in der Verwendung des Speichers.

Intuitiv haben DFAs überhaupt keinen Arbeitsspeicher. Die Konfiguration eines DFA hängt vollständig von dem Zustand ab, in dem er sich gerade befindet, und von seinem aktuellen Fortschritt beim Lesen der Eingabe.

Intuitiv haben TMs einen "Kratzer" -Speicher in Form von Bändern; Die Konfiguration eines TM besteht sowohl aus seinem aktuellen Status als auch aus dem aktuellen Inhalt des Bandes, den der TM während der Ausführung ändern kann.

Ein DFA kann als TM betrachtet werden, das weder Bandsymbole ändert noch den Kopf nach links bewegt. Diese Einschränkungen machen es unmöglich, bestimmte Sprachen zu erkennen, die von TMs akzeptiert werden können.

Beachten Sie, dass ich den Begriff "DFA" anstelle von "FSM" verwende, da ich ein TM technisch als eine endliche Zustandsmaschine betrachten würde, da TMs per Definition eine endliche Anzahl von Zuständen haben. Der Unterschied zwischen DFAs und TMs besteht in der Anzahl der Konfigurationen, die der Anzahl der Status für einen DFA entspricht, für einen TM jedoch unendlich groß ist.

Patrick87
quelle
Ah, verstanden. Eine Frage zum Teil "kein Gedächtnis": Ich habe ein Automatenbeispiel gesehen, das die ausgegebenen Münzen addiert. Woher wissen sie, wie viel Geld da ist, wenn es kein Gedächtnis hat?
Julio Garcia
@ Julio Garcia Es ist schwer zu sagen, ohne genau zu wissen, was Sie gesehen haben. Es gibt Moore- und Mealy-Maschinen, die Symbole bei Übergängen ausgeben können. Die Aktivität eines Verkaufsautomaten könnte durch einen dieser Mechanismen besser modelliert werden. Ein Vanille-DFA akzeptiert nur Zeichenfolgen und lehnt diese ab ... ein Verkaufsautomat sollte jede "Zeichenfolge" von Münzen "akzeptieren". Abhängig davon, wie Sie die zusätzlichen Nebenwirkungen von Änderungen modellieren, ist möglicherweise kein oder ein unbegrenzter wahlfreier Zugriff erforderlich.
Patrick87
Ohne Ihr Beispiel zu sehen, kann ich nicht ganz sicher sein, aber ich habe zwei Vermutungen. Einer ist, dass es nicht weiß, wie viel Geld da ist: Es wird nur angenommen, dass es genug gibt. Sie möchten so keinen echten Verkaufsautomaten bauen, aber es ist immer noch ein nützliches Beispiel für das Konzept. Die andere Möglichkeit ist, dass es sich nicht wirklich um eine "reine" FSA handelt: Sie ist an einen Sensor angeschlossen, der diese Daten irgendwie von "außerhalb" der Maschine abrufen kann. Das Gerät weiß nicht, woher die Daten kommen, und es kann nichts im Sensor speichern (es ist also nicht wirklich "Speicher"), aber es kann trotzdem auf das einwirken, was es dort sieht.
The Spooniest
16

Turing Machines beschreiben eine viel größere Klasse von Sprachen, die Klasse von rekursiv aufzählbaren Sprachen. Finite-State-Maschinen beschreiben die Klasse der regulären Sprachen.

Endliche Zustandsmaschinen haben kein "Gedächtnis", sie sind durch ihre Zustände begrenzt.

Eine Finite-State-Maschine ist eine eingeschränkte Turing-Maschine, bei der der Kopf nur "Lese" -Operationen ausführen kann und sich immer von links nach rechts bewegt.

Nehmen Sie diese Sprache als Beispiel:

L={aibi| i>=0}

Da Zustandsmaschinen in dem Sinne begrenzt sind, dass sie keinen Speicher haben, kann eine FSM, die L akzeptiert, nicht konstruiert werden.

Zusammenfassen:

Finite-State-Maschinen beschreiben eine kleine Klasse von Sprachen, in denen kein Speicher benötigt wird.

Turing Machines sind die mathematische Beschreibung eines Computers und akzeptieren eine viel größere Klasse von Sprachen als FSMs.

Turing Machines haben mehr Rechenleistung als FSM. Es gibt Aufgaben, die kein FSM ausführen kann, die Turing Machines jedoch ausführen können.

mrjasmin
quelle
3

Ich hatte den gleichen Zweifel und sah zwei sehr aufschlussreiche Videos und eine Erklärung zu Quora wie folgt:

Eine Zustandsmaschine ist nur eine Reihe von Zuständen und Übergängen. Der einzige Speicher, den es hat, ist der Zustand, in dem es sich befindet. Somit ist die Anzahl der Speicherzustände ... endlich.

Eine Turing-Maschine ist eine Finite-State-Maschine mit einem Bandspeicher. Jeder Übergang kann von einer Operation auf dem Band begleitet sein (Verschieben, Lesen, Schreiben).

Ich habe daraus verstanden, dass eine Turing-Maschine eine endliche Zustandsmaschine als Teil ihrer Betriebsprozedur verwendet / hat und zusätzlich einen bearbeitbaren Speicher hinzufügt.

Bitte schau dir auch diese beiden Videos an, sie sind aufschlussreich!

https://youtu.be/gJQTFhkhwPA

https://youtu.be/E3keLeMwfHY

user5193682
quelle
2

Soweit ich die Unterschiede zwischen (Standardmodell) Turing und (Standardmodell) Mealy Machines verstehe:

  • Turingmaschinen Lesen und Schreiben auf demselben Band vs. Mealy Maschinen lesen auf einem Eingabeband und schreiben auf einem anderen Ausgabeband
  • Turing Machines können die "Bandrichtung" ändern (nach links oder rechts gehen [oder anhalten]) vs. Mealy Machines können nur nach rechts gehen (deshalb gibt es in der Übergangsfunktion der Mealy Machine keine Richtungsangabe {L, R, H} [es ist implizit {R}, was bedeutet, dass es überhaupt keine Wahl gibt])
  • Turing Machines können auf jeder Bandzelle anhalten, während Mealy Machines die gesamte Eingabe lesen und sie dann nicht mehr akzeptieren oder ablehnen
Michael Klaube
quelle
-3

Eine Turing-Maschine kann als Teil des Bands Dinge speichern, an die sie sich erinnern möchte.

richard mullins
quelle
5
Es ist nicht klar, was Sie mit "es" meinen, aber sowohl Turing-Maschinen als auch FSMs können dies tun, sodass es keinen Unterschied gibt.
David Richerby
@DavidRicherby Ein FSM kann jedoch nur eine vorgegebene Menge speichern, wohingegen Turing-Maschinen so viel speichern können, wie sie möchten. Das ist der grundlegende Unterschied.
Gilles 'SO- hör auf böse zu sein'
1
@ Gilles Einverstanden, aber das ist nicht, was die Antwort sagt.
David Richerby