Die zeigen, dass die Reihe von TMs, die besuchen Sie die Start-state doppelt auf die leere Eingabe ist unentscheidbaren

Question

Ich bin versucht zu beweisen, dass

$L_1=\{\langle M angle \mid M ext{ ist eine Turing-Maschine und Besuche } q_0 ext{ mindestens zweimal } \varepsilon\} otin R$.

Ich bin mir nicht sicher, ob zu reduzieren das Halteproblem oder nicht.Ich habe versucht zu konstruieren, eine neue Maschine $M'$ für $(\langle M angle,w)$, so dass $M'$ besucht $q_0$ zweimal, iff $M$ die halte auf $w$.Dies ist spezifisch $q_0$, die mir gegeben, aber ich kam nicht, um eine intelligente Konstruktion, die sich ergeben würde ersuchten.Vielleicht ist es einfacher zu zeigen, dass es $RE$ und nicht $coRE$?Es ist offensichtlich, dass es in $RE$, und ich brauche, um zu zeigen, dass $L_2^{c}$ ist nicht in $RE$.

Was soll ich tun?

Answer 1

Machen Sie nicht diese komplizierter, als es ist.Stattdessen geben wir Ihnen eine volle Lösungen, ich werden geben Sie eine teilweise Lösung, die ermöglichen sollte, Sie zu erarbeiten die details selbst:

Jeder TM gedreht werden in ein TM-Besuche, die in seinen ursprünglichen Zustand genau einmal.Zu tun so, eine neue Zustand $q^'_0$, die das neue start-state.Fügen Sie dann ein $\varepsilon$-übergang von $q^'_0$ in $q_0$.Dies ist der einzige Weg, um "verlassen" der Staat $f'_0$.

Für diese modifizierte-Maschine, die Annahme ausführen Besuche den Ausgangszustand einmal, und endet in den akzeptierenden Zustand.Was noch zu tun ist, ändern die Maschine weiter, so dass es springt zurück zu $q^'_0$, nachdem die Maschine war in den akzeptierenden Zustand.Aber Sie haben zu versichern, dass, wenn $f^'_0$ ist besucht, das zweite mal, Sie wird springen, um eine neue zu akzeptieren Staat.Aber es ist nicht schwer, zu erfassen, wie oft Sie besucht eine Staatliche.

Wenn Sie möchten, dass ein anderer Staat ist zweimal besucht, dann kann man immer einen kleinen Umweg gemacht am Anfang, dass Besuche in diesem Zustand Sie Rekord, dass die Maschine in den "Umweg" - Modus schreiben eine Flagge auf einem speziellen Klebeband).Als Sie umleiten die normale Berechnung, so dass, wenn Sie es besuchen sollten der ersuchte Staat besucht er eine Kopie von diesem Zustand.Schließlich, wenn Sie akzeptieren, springen Sie zurück an den ersuchten Staat.Konzeptionell ist dies nicht sehr unterschiedlich zu Umetikettierung der Staaten.