Wie zeichnet man eine Ergänzung einer Turingmaschine?

7

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 '

Geben Sie hier die Bildbeschreibung ein

Dana
quelle
crossposted
Austin Buchanan
setze ein beinr¯darüber: p
vzn
Im Ernst, Sie müssen zum Defn des TM zurückkehren und bestimmen, was es in jedem Fall von "Palendrom erkannt" und "kein Palendrom" tut ... es schreibt wahrscheinlich einen bestimmten "Status" auf das Band ... Sie müssen es neu codieren, um diesen "Status" "umzudrehen" ... trotzdem ist der Titel der Frage irreführend, er kann nicht nur "gezeichnet" werden, sondern erfordert eine Neukonfiguration der Statustabelle, insbesondere der Zustände am nächsten Ende.
vzn
1
Startzustände in Endzustände umzuwandeln und umgekehrt ist nicht die Art und Weise, wie Sie einen DFA ergänzen. (DFAs haben nicht einmal "Endzustände".) DFAs werden ergänzt, indem akzeptierende Zustände in nicht akzeptierende Zustände umgewandelt werden und umgekehrt.
David Richerby

Antworten:

11

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.

babou
quelle
Sie sagen also, dass Sie nicht alles tun können, indem Sie eine Ergänzung zu TM machen oder nur in diesem Problem? ... Ich weiß, dass es möglich ist, es in FA zu tun ...
Dana
es ist nicht so einfach wie "das Ja und das Nein auszutauschen" oder vielmehr, dass einige Details
verborgen sind
1
@Dana: FAs sind nicht so leistungsfähig wie TMs, daher ist es nicht verwunderlich, dass sie andere Verschlusseigenschaften haben sollten.
Raphael
@vzn Habe ich auf deine Sorgen geantwortet? (
Haben Sie
+8? Diese Zeile macht nicht viel Sinn. "Nicht deterministische Maschinen machen das Gegenteil: Wenn sie" Ja "sagen, bedeutet dies" Ja ", und wenn sie" Nein "sagen, bedeutet dies" Vielleicht ". Es ist auch" Vielleicht ", wenn sie schweigen (immer noch nachdenken), aber das ist immer wahr. "
vzn