Ich bin jetzt ziemlich zuversichtlich, wie ich etwas in eine Turingmaschine verwandeln würde. Meine Frage ist nun, wie Sie TM in eine Ergänzung einer Turingmaschine umwandeln können. Soweit ich mich in Finite Automata erinnern kann, würden Sie als Ergänzung einen Startzustand in einen Endzustand verwandeln. Wenn Sie einen Endzustand haben, würden Sie ihn in einen Startzustand verwandeln. Wie würden Sie eine Turingmaschine ergänzen?
Zum Beispiel habe ich hier ein einfaches TM eines Palindroms und ich möchte ein Palindrom '
Antworten:
Sie können es im Allgemeinen nicht tun.
Es würde die Ergänzung Ihrer Sprache halbentscheidbar machen, wie die Sprache selbst. Daher wären beide entscheidbar, wenn beide Maschinen parallel laufen würden.
Dies betrifft natürlich nur den Fall von halbentscheidbaren Sprachen, für die das TM nicht immer für Wörter anhält, die nicht in der Sprache sind.
Wenn Sie eine entscheidbare Sprache haben, für die das TM immer mit einem Ja oder Nein stoppt, tauschen Sie einfach das Ja und das Nein aus.
Es sind jedoch einige Vorsichtsmaßnahmen zu treffen:
Kompatibilität von akzeptierenden und nicht akzeptierenden Konfigurationen
Abhängig von Ihrer gewählten Definition von Turing-Maschinen ist das Akzeptieren und Anhalten nicht akzeptierender Konfigurationen möglicherweise nicht kompatibel und daher möglicherweise nicht austauschbar. Wenn es einem akzeptierenden Zustand erlaubt ist, Übergänge zu haben, die verwendet werden könnten, kann die Berechnung nur fortgesetzt werden, anstatt anzuhalten, ohne zu akzeptieren. Daher müssen einige recht einfache Vorsichtsmaßnahmen getroffen werden, wie Akzeptanz und Ablehnung identifiziert werden und wie sie ausgetauscht werden können.
nicht deterministische Maschinen
Nicht deterministische Maschinen sind Anti-Manager. Wenn ein Manager "Nein" sagt, bedeutet dies "Nein", und wenn er "Ja" sagt, bedeutet dies "Vielleicht".
Nicht deterministische Maschinen machen das Gegenteil: Wenn sie "Ja" sagen, bedeutet dies "Ja", und wenn sie "Nein" zu sagen scheinen (Anhalten in einer nicht akzeptierenden Konfiguration), bedeutet dies "Vielleicht". Der Grund dafür ist vielleicht, dass es mit einer anderen nicht deterministischen Auswahl einiger Übergänge mit Ja geantwortet hat. Tatsächlich sollten nicht deterministische Automaten genauer gesagt niemals eine negative Antwort geben. Es ist praktisch mit deterministischen Automaten, bedeutet aber nichts mit nicht deterministischen. Es ist auch "vielleicht", wenn sie aus zwei Gründen nicht beendet werden: (1) Eine andere Übergangswahl hat möglicherweise zu einer Akzeptanz geführt, und (2) Sie können keine Nichtakzeptanz geltend machen, da die Berechnung möglicherweise fortgesetzt wird.
Daher ist es nicht einfach, eine Sprache zu ergänzen, die von einem nicht deterministischen oder nicht haltenden Gerät erkannt wird. Sie können nicht einfach "Ja" und "Nein" austauschen, da Sie nur "Ja" und "Vielleicht" haben. Sie würden nur eine Verwaltungsmaschine erhalten, die nur mit "Nein" oder "Vielleicht" antwortet und von der Automata Theory Union nicht anerkannt wird. Automaten müssen akzeptieren, indem sie "Ja" eindeutig beenden und beantworten, wenn das zu erkennende Wort in der Sprache vorliegt. In einigen Fällen mit Nein antworten zu können, ist nur ein Bonus deterministischer Maschinen, wenn sie so freundlich sind, anzuhalten.
Sie müssen also zuerst Ihre Maschine in eine deterministische umwandeln. Dann können Sie akzeptierende und ablehnende Konfigurationen austauschen (unter Berücksichtigung des vorherigen Punktes oben), vorausgesetzt, dass die Maschine immer anhält.
Um die Ergänzung eines regulären Satzes zu erhalten, ist es zweckmäßig, zuerst einen DFA zu erstellen, der ihn erkennt.
Eine Turing-Maschine kann immer in eine deterministische verwandelt werden, aber sie kann nicht anhalten und so Raum für "vielleicht" lassen. Daher ist es nicht immer möglich, eine von einer Turingmaschine erkannte Sprache zu ergänzen, wie oben angegeben. Es ist jedoch möglich, dass ein (determiniertes) TM immer mit einer Ja / Nein-Antwort stoppt.
quelle