Mostra che il problema della terminazione è decidibile per le macchine di Turing passa-uno

Question

$ L = \ {<\! M, x \!> \, \ A metà M \ text {funzione di transizione può muovere solo a destra e} M \ text {} ferma su x \} $. Ho bisogno di dimostrare che $ L $ è ricorsiva / decidibile.

ho pensato di controllare la codifica di $ M $ prima e determinare se le sue mosse funzione di transizione solo a destra (posso farlo?). Se è così allora cercare di simulare $ M $ a $ x $ per $ | Q | + 1 $ passi, se si ferma quindi \, $ \ In L $ in caso contrario non è

È corretto?

Answer 1

Presumo $ Q $ è insieme stato di $ M $. Se è così, questo runtime legato non ha molto senso; in particolare, una macchina di Turing con tre stati può spostarsi alla fine dell'input e controllare se $ x $ è un numero pari; chiaramente non è sufficiente aspettare tre passi.

La prossima domanda è se ci è un calcolabile legata al tempo di esecuzione delle macchine passa-uno di sosta. Purtroppo, non c'è:. $ M $ potrebbe essere non deterministico e battuta d'arresto dopo una quantità arbitraria di passi

Così abbiamo determinise $ M $, mentre la simulazione (che è calcolabile) e cercare un diretto a tutti i percorsi. Ora stiamo ottenendo da qualche parte: dopo aver consumato l'ingresso, ci sono due casi. Sia $ M $ soste o si entra in un ciclo. Come si muove solo a destra (in nastro vuoto), tali cicli possono essere rilevate.

Mettendo insieme le cose, abbiamo simulare una determinisation di $ M $. Noi usiamo ogni ramo fino a $ x $ è consumed¹ e poi per un altro $ | D | \ cdot | \ Sigma_T | $ gradini, $ Q $ l'insieme di stati e $ \ Sigma_T $ l'alfabeto del nastro di $ M $. A questo punto $ M $ ha arrestato o loop (in questo ramo), che rileviamo da una coppia di corrente occuring stato e nastro simbolo per la seconda volta. Dobbiamo solo controllare un numero finito di rami fino a un limite calcolabile, quindi $ L $ è ricorsiva.

---

1. $ M $ forze ciclo già qui, se non si muove la testa è consentito, ma che può essere rilevato, anche.