Bei einer TM -

Ich möchte feststellen, ob dieses Entscheidungsproblem entscheidbar ist. Ich habe versucht, Reduzierungen von Halt und "Akzeptiert leere Zeichenfolgen" zu ermitteln, habe jedoch noch keine Lösung gefunden.

Kann mir jemand helfen?

computability turing-machines undecidability Shuzheng
quelle

Dies bedeutet, dass die Maschine an derselben Stelle bleiben sollte, keine Bewegungen. Es gibt nicht viele Möglichkeiten für eine solche Berechnung?

Hendrik Jan

Es könnte sich tatsächlich bewegen. Aber dann annehmen , daß für einigen Zustand , bezeichnet und . Was können Sie über den Fall sagen ? Was passiert als nächstes, wenn ?

δ (q_{0},_) = (q, a, D)

$\delta(q_0,\_) = (q,a,D)$

q

$q$

a

$a$

D \in {L, R}

$D\in\{L,R\}$

q \neq q_{0}

$q\neq q_0$

q = q_{0}

$q = q_0$

Klaus Draeger

Dieses Problem kann entscheidbar sein. Ich habe dieses Papier hal.inria.fr/inria-00074105 gefunden (ich habe es nicht gelesen, bin mir also nicht sicher), das Sie interessieren könnte. Es wird behauptet, dass das Stoppproblem für eine Turing-Maschine mit einem Zustand entscheidbar ist. (Das ist ein Problem, das Ihrem Problem ziemlich nahe kommt).

Wece

Bitte ändern Sie den Titel der Frage "... wenn das Startband leer ist", wenn es sich bei Ihrem Kopfgeld um "irgendeine Bandeingabe" handelt: Der Fall, in dem das Band balnk ist, ist trivial entscheidbar (ich habe eine Antwort gepostet, aber ich habe sie plötzlich gelöscht, wenn Ich habe den Kommentar zum Kopfgeld gesehen)

Vor

Antworten:

Ich würde sagen, es ist entscheidbar.

Wenn ich richtig verstanden habe, denke ich Folgendes.

Zunächst startet ein TM von einem Anfangszustand . Wie kann es den Zustand ändern? In Ihrer Übergangsfunktion haben Sie so etwas wie wobei ein Zustand ist und , $s_0$ $(s_0, x) \to (s_i, y, m)$ $s_i$ $x$ $y$ Symbole sind und die Kopfbewegung ist (links rechts oder bleiben). Wenn es also den Anfangszustand verlässt, sollte es einen Übergang von zu einem Zustand geben, der nicht . Leicht zu erkennen, dass es genau dann ist, wenn. Auf diese Weise können Sie eine andere Turing-Maschine erstellen, die die Eingabe in einer bestimmten Codierung als TM hat, die Übergangsfunktion durchläuft und die obige Bedingung überprüft, und das Problem ist entscheidbar. $m$ $(s_0, \_)$ $s_0$

Eugene
quelle

s_{0}

$s_0$

s_{0}

$s_0$

@ DW Sprechen wir hier über deteministisches oder nicht deterministisches TM?

Eugene

Das ist eine Frage, die Sie dem Originalplakat stellen sollten, wenn Sie der Meinung sind, dass es unklar ist, aber mit den gegebenen Informationen sollten wir ein deterministisches TM annehmen. Ich vermute jedoch, dass ich von dem Kopfgeldtext beeinflusst wurde, der sich auf ~ "verlässt nie den Anfangszustand, unabhängig von einem Anfangszustand des Bandes" ~ bezieht, was ein bisschen anders ist als "verlässt nie den Eingangszustand, wenn der Anfangszustand" Der Zustand des Bandes ist völlig leer. "Vielleicht ist mein Einwand für die gestellte Frage irrelevant.

Wie auch immer, vielleicht würde es helfen, den Teil "leicht zu sehen ..." sorgfältiger zu rechtfertigen. Zum Beispiel scheinen Sie die Tatsache, dass das ursprüngliche Band leer ist, nicht explizit zu verwenden, obwohl es den Anschein hat, dass dies einen großen Unterschied macht.

$s_0$ $s_0$ $s_0$ $s_0$ $s_0$ (einschließlich 'angehalten'), lautet die Antwort JA Andernfalls lautet die Antwort NEIN.

Ich bin mir auch ziemlich sicher, dass das Problem bei willkürlicher Eingabe immer noch entscheidbar ist - Sie müssen nur genauer darauf achten, in welche Richtung sich der Bandkopf abhängig vom aktuellen Zelleninhalt bewegt.

PMar
quelle