Dimostrando che l'insieme di TM che visitano lo stato di base due volte sull'ingresso vuoto è indecidibile

Question

sto cercando di dimostrare che

$ L_1 = \ {\ langle M \ rangle \ metà M \ text {è una macchina di Turing e le visite} Q_0 \ text {almeno due volte sul} \ epsilon \} \ notin R $.

Non sono sicuro se ridurre il problema della terminazione ad esso o meno. Ho cercato di costruire una nuova macchina $ M '$ per $ (\ langle M \ rangle, w) $, in modo tale che $ M' $ visite $ Q_0 $ due volte, IFF $ M $ ferma su $ w $. Questo è specifico $ Q_0 $ dato a me, ma io non sono venuto a qualsiasi costruzione intelligente, il che produrrebbe l'ha richiesto. Forse è più facile mostrare che si tratta di $ RE $ e non $ CORE $? E 'ovvio che si trova in $ RE $, e ho bisogno di dimostrare che $ L_2 ^ {c} $ non è in $ RE $.

Che cosa devo fare?

Answer 1

Non fare questo più complicato di quanto non sia. Invece di dare voi un soluzioni complete, vi darò una soluzione parziale, che dovrebbe consentire di definire i dettagli da soli:

Ogni TM essere trasformato in una TM che le visite allo stato iniziale esattamente una volta. Per fare ciò, introdurre un nuovo stato di $ q ^ '_ 0 $, che sarà il nuovo stato di partenza. Quindi aggiungere un $ \ varepsilon $ Transizione da $ q ^ '_ 0 $ a $ Q_0 $. Questo è l'unico modo per "congedo" lo stato $ q'_0 $.

Per questa macchina modificata, accettando un eseguire le visite lo stato iniziale una volta, e si conclude nello stato accettato. Ciò che resta da fare è modificare la macchina ulteriormente, in modo tale che salta di nuovo a $ q ^ '_ 0 $, dopo che la macchina era in stato di accettazione. Ma bisogna assicurare che quando $ q ^ '_ 0 $ è visitato per la seconda volta, si salta a un nuovo stato accettante. Ma non è difficile registrare quante volte avete visitato uno stato.

Se si vuole che un altro Stato è visitato due volte, allora si può sempre fatto una deviazione in principio che le visite questo stato (si registrano che la macchina è in modalità "deviazione" scriverà una bandiera su un nastro speciale). Di quello che reindirizzare il calcolo normale, in modo tale che se dovesse visitare lo Stato richiesto si visita una copia di questo stato. Infine, quando accetta, si passa allo stato richiesto. Concettualmente, questo non è molto diverso da rietichettatura gli stati.