Turiermaschine, die sich erinnern kann

Question

Special-Turing-Maschine ist ebenso wie Standard-Turing-Maschine definiert, nur dass jeder Schritt entsprechend dem Gehalt des Bands gestartet wird, beginnend von der linken Kante bis zur Kopfposition in Band. (Die Übergangsfunktion in diesem Fall gehört zu q x γ * -> q x γ x {l, r})

Welches der folgenden ist wahr:

a. Jede Sprache L hat eine Turing-Maschine, die danzieht, wenn und nur, wenn es eine spezielle Turing-Maschine gibt, die l.

b. Jede Sprache L hat eine Turing-Maschine, die in einer Polynomzeit, wenn und nur, wenn es eine spezielle Turierungsmaschine entscheidet, die L in einem Polynom (Eingangslänge Polynom) entscheidet.

c. A, B-Antworten sind korrekt.

d. A, B-Antworten sind falsch.

und meine Frage ist: Die richtige Antwort ist d und ich kann nicht verstehen, warum.

Die Antwort ist: Jede Sprache kann von einer speziellen Turingmaschine in der linearen Eingangslängenzeit (O (n) entschieden werden, wenn n die Eingangslänge ist). Eine Übergangsfunktion geht nach rechts, solange kein Leerzeichen zu sehen ist, und sobald Sie einen leeren Raum sehen, um den auf dem Band geschriebenen Wort zu empfangen oder abzulehnen.

meine Frage ist: Wie kann ich entscheiden, ob ein Wort abzulehnen oder akzeptiert wird? Bei anderen Rechenmodellen wie PDA, DFA haben wir die Übergangsfunktion in ähnlicher Weise definiert, und dem Modell wurde keine Stromversorgung hinzugefügt. Warum scheint es, dass das Rechenmodell infolge der Änderung der Übergangsfunktion in Bezug auf Turing-Maschinen in das Rechenmodell hinzugefügt wird?

danke.

Answer 1

Angesichts einer beliebigen Sprache $ L $ Es gibt eine spezielle Turing-Maschine $ t $ , die $ L $ bei der Polynomzeit.

Die Turing-Maschine verfügt über 3 Zustände: Die Anfangszustände $ q_0 $ , der akzeptierende staatliche $ q_a $ und der Ablehnungszustand $ q_r $ . $ \ gamma $ Seien Sie das Bandalphabet (einschließlich des leeren Symbols $ \ VAREPSILON $ ), und lassen Sie sie $ \ alpha x $ Bezeichnen Sie den Inhalt des Bands, das von der linken Kante bis zur Kopfposition in Band beginnt, wobei $ \ Alpha \ in \ gamma ^ * $ und $ x \ in \ gamma $ . Ich gehe wie üblich davon aus, dass der Eingang ab dem Anfang des Bands geschrieben wird und der Kopf anfangs am Anfang des Bands positioniert ist. Die Übergangsfunktion $ \ DELTA $ ist wie folgt definiert:

.
• $ \ DELTA (Q_0, \ alpha x)= (q_0, x, r) $ Wenn $ X \ NEQ \ VAREPSILON $
• $ \ DELTA (Q_0, \ alpha x)= (q_a, x, r) $ Wenn $ x=VAREPSILON $ und $ \ alpha \ in L $
• $ \ DELTA (Q_0, \ alpha x)= (q_a, x, r) $ Wenn $ x=VAREPSILON $ und $ \ alpha \ nicht \ in L $

Da es unentdeckbare Sprachen für reguläre Turing-Maschinen gibt, bedeutet dies sofort, dass A und B falsch sind.

Antworten D und C sind unklar. Sie sprechen über "Antworten", aber Sie erhalten $ 4 $ mögliche Antworten.