Turing-Maschinen verstehen: Erkennbare und entscheidbare Sprachen

Ich habe Tonnen von Ressourcen durchsucht und obwohl ich die Turing-Maschine selbst und ihre Funktionsweise konzeptionell verstehe, hänge ich ein wenig an Turing Recognizable- und Turing Decidable-Sprachen fest und bin mir nicht sicher, ob die Idee, die ich über sie habe, richtig ist oder falsch.

Mein Professor definiert vier mögliche Aktionen, die eine Turing-Maschine mit einer bestimmten Eingabezeichenfolge ausführen kann:

  • Hängen: Die Turing-Maschine löst sich vom linken Ende des Bandes und „hängt“
  • Schleife: Die Turing-Maschine dreht sich in einer Schleife – hält nie an
  • Akzeptiert: Die Turing-Maschine hält in einem akzeptierenden Zustand an
  • Ablehnungen: Die Turing-Maschine stoppt in einem Ablehnungszustand

Ist eine erkennbare Sprache nur eine, die entweder hängen oder sich wiederholen kann? Wie kann ich feststellen, ob es hängen oder schleifen kann? Lassen Sie es einfach durch die Maschine laufen und wenn es nicht auf dem ablehnenden Zustand (oder Akzeptieren) stehen bleibt und es nicht Teil der Sprache des TM ist, dann bestimme ich, dass es nicht entscheidbar ist – also muss es erkennbar sein? Und dann ist die Entscheidung, ob die Sprache garantiert akzeptiert oder ablehnt? Was ist mit Sprachen, die nicht erkennbar sind? Was würden sie tun? Denn es scheint, dass alle Sprachen erkennbar wären, es sei denn, es wäre möglich, dass die Sprache nicht die Sprache der Turing-Maschine ist – aber sie hält sowieso im akzeptierenden Zustand an. Was anscheinend eher auf ein schlechtes Design der Turing-Maschine als auf die Sprache selbst zurückzuführen ist.

Ich habe nur Mühe, diese beiden Definitionen zu verstehen. Ich habe stundenlang für meine Prüfung gelernt, die morgen ist, und ich kann einfach nicht begreifen, was ein einfaches Konzept sein sollte. Bitte helfen Sie, meine Verwirrung aufzuklären?

Ich weiß nichts über Hänge, das ist ein unnötiges Konzept. Turing entscheidbar bedeutet, dass es in einem akzeptierenden Zustand anhält, wenn das eingegebene Wort in der Sprache ist, und in einem ablehnenden Zustand anhält, wenn das Wort nicht in der Sprache ist, Turing erkennbar bedeutet, dass es in einem akzeptierenden Zustand anhält, wenn das Wort in der Sprache ist. und in einem ablehnenden Zustand oder hält nicht an, wenn das Wort nicht in der Sprache ist. Es gibt Sprachen, die nicht erkennbar sind. Das einfachste Argument ist ein Kardinalitätsargument. Es gibt unzählbar viele Sprachen und nur zählbar viele Turingmaschinen.

Antworten (1)

Eine Sprache L heißt rekursiv aufzählbar, wenn es eine Turingmaschine gibt M die folgenden Bedingungen erfüllen:
-Für jeden ω ∈ L , simulieren M An ω (was wir bezeichnen M ( ω ) ) ergibt M innehalten und annehmen ω . -Für jeden ω ∈ Σ ∗ ∖ L , M akzeptiert nicht ω .

Beachten Sie, dass für eine rekursiv aufzählbare Sprache jedes TM akzeptiert L braucht bei Eingaben außerhalb der Sprache nicht anzuhalten.

Wenn L entscheidbar ist, muss es zusätzlich zu den Bedingungen für eine TM geben, die bei allen Eingaben anhält L rekursiv aufzählbar.

Was ist mit Sprachen, die nicht erkennbar sind?

Kein solcher Entscheider oder Erkenner würde existieren. Betrachten Sie die folgende Sprache: L N Ö T − H A L T = { ⟨ M ich ⟩ , ω ich : M ich ist der ich TM und ω ich ist der ich te Saite rein Σ ∗ Und M ich hält nicht an ω ich } .

Die Sprache L N Ö T − H A L T ist nicht rekursiv aufzählbar. Kein TM kann jede Zeichenfolge akzeptieren M ich . Für einige TMs in L N Ö T − H A L T , ist es möglich, eine Endlosschleife zu erkennen, indem man die Zustände und die Übergangsfunktion überprüft. Es gibt jedoch kein allgemeines Verfahren, um dies für alle TMs in zu tun L N Ö T − H A L T . Ein Cantor-Diagonal-Argument beweist dies. Siehe die Unentscheidbarkeit des Halteproblems.

Klärt das die Sache auf?

Turing-Maschinen verstehen: Erkennbare und entscheidbare Sprachen
AntwortenHierDatenschutz-Bestimmungen1y, 2v