Was ist der Unterschied zwischen einem TM, der eine Sprache akzeptiert und entscheidet?

Ehrlich gesagt fühle ich mich gerade sehr unwohl mit dem Material. Es gibt einige Dinge, die ich verstehen kann, aber viele, die ich immer noch nicht verstehe.

Meine erste Aufgabe besteht darin, mich in einer Frage (die ich zu tun weiß) zu bitten, eine vollständige Beschreibung eines TM zu geben, das eine Sprache akzeptiert . Ich weiß, dass jede binäre Zeichenfolge, die mit endet, durch 4 teilbar ist. die Sprache, die dieses TM akzeptiert.$L = \{ x \in \{0,1\}^* \mid x \text{ is divisible by } 4 \}$$00$$\{00,100,1100,1000,11100,11000,10100,10000,\dots\}$

Aber zum Thema (Un-) Entscheidbarkeit: Ich weiß, dass eine Sprache entscheidbar ist, wenn es ein TM gibt, das alle Zeichenfolgen und nur Zeichenfolgen aus dieser Sprache akzeptiert - und dasselbe TM lehnt alle Zeichenfolgen und nur Zeichenfolgen ab, die nicht in dieser Sprache enthalten sind.

Was zu der Frage führt: Was ist der Unterschied zwischen einer Turing-Maschine , die eine Sprache akzeptiert und entscheidet ?

In Situationen wie diesen, in denen Sie sich über den Unterschied zwischen zwei Phrasen wundern, ist es richtig, einige Definitionen nachzuschlagen und darüber nachzudenken. Sie werden verschiedene Variationen entdecken, vielleicht so etwas:

1. Eine Maschine "isst" eine Sprache wenn sie bei Eingabe anhält und ausgibt, wenn , und wenn dies nicht der Fall ist .$L$$x$$1$$x \in L$$0$

2. Eine Maschine "trinkt" eine Sprache wenn sie bei Eingabe in einem Zustand anhält, in dem und in einem Zustand, in dem .$L$$x$accept$x \in L$reject$x \not\in L$

3. Eine Maschine „sniffs“ Sprache , wenn am Eingang in einem stoppt Zustand , wenn und niemals endet , wenn .$L$$x$accept$x \in L$$x \not\in L$

4. Eine Maschine "verschlingt" eine Sprache wenn sie bei Eingabe einen Zustand erreicht, wenn und sonst niemals in den Zustand eintritt .$L$$x$OK$x \in L$OK

5. A machine „kaut“ eine Sprache , wenn am Eingang in Zustand hält , wenn und entweder nie beendet wird oder stoppt in dem Zustand , wenn .$L$$x$0$x \in L$1$x \not\in L$

Diese sehen alle gleich aus, sind aber alle leicht unterschiedlich. Sie sollten erwarten, dass einige Definitionen leicht gebrochen sind (weil Sie sie aus Wikipedia oder den Notizen Ihres Klassenkameraden erhalten haben) oder auf eine seltsame Weise formuliert sind, die den Anforderungen eines bestimmten Texbooks usw. entspricht.

Das Wichtigste ist, herauszufinden, was die Definitionen wirklich zu vermitteln versuchen. Wenn es sich um grundlegende Definitionen handelt, auf die sich jeder bezieht, werden sie Ihnen wahrscheinlich etwas Wichtiges sagen. (In einem Forschungsbericht machen Menschen manchmal Definitionen, um das Gehirn der Leser zu betäuben.) Sobald die Konzepte klar sind, spielt es keine Rolle, wie sie genannt werden. Im Falle einer terminologischen Verwirrung können Sie mögliche Missverständnisse immer schnell beheben, da Sie bereits wissen, welche Konzepte zu erwarten sind.

Im vorliegenden Fall gibt es tatsächlich zwei mögliche Begriffe. Eine, bei der eine Maschine immer anhält und auf irgendeine Weise Akzeptanz / Nichtakzeptanz signalisiert, beispielsweise durch Anhalten in bestimmten Zuständen oder durch Ausgeben bestimmter Symbole. Das andere Konzept ist, wenn eine Maschine nicht immer anhält und das Anhalten verwendet, um die Akzeptanz anzuzeigen, und das Nicht-Anhalten, um die Nichtannahme anzuzeigen.

Eine schöne Übung besteht darin, herauszufinden, welche der fünf oben angegebenen Definitionen welchem ​​der beiden Konzepte entspricht (und welche Definition, falls vorhanden, etwas unklar ist). Aber schon vor der Übung müssen Sie wissen, warum dies zwei verschiedene Konzepte sind! Sie müssen sich einer Sprache bewusst sein, die unter das eine, aber nicht unter das andere Konzept fällt.

Das Problem beim Erlernen von Mathematik besteht darin, dass Sie gleichzeitig neue Sätze und deren Bedeutung lernen und herausfinden müssen, warum die Leute sie erfunden haben.

Es gibt einen großen Unterschied. Eine Turingmaschine "akzeptiert" eine Sprache, wenn sie für eine Eingabe aus der Sprache in einen akzeptierenden Zustand wechselt, während sie die Sprache "entscheidet", wenn sie sie "akzeptiert" und für jede Eingabe, die nicht in der Sprache enthalten ist, in einen Ablehnungsstatus wechselt.

Diese sind unterschiedlich, weil es eine dritte Sache gibt, die eine Turing-Maschine tun kann: niemals aufhören. Eine solche Turing-Maschine akzeptiert die Sprache, entscheidet sie aber nicht.

Siehe auch diese andere Frage und Definition der entscheidbaren Sprache in WP .

Sie werden normalerweise als Synonyme verwendet. In Ihrem Beispiel sollte die Turing-Maschine zuerst bis zum Ende der Eingabe gehen und dann überprüfen, ob die beiden Ziffern ganz rechts 0 sind, wie Sie vorschlagen.