Proving esistenza di TM che accetta la lingua successiva

Question

Ho un'idea di come avvicinarsi al problema, ma non ne sono sicuro. Data una macchina di tenuto, posso controllare quanti stati ha la macchina, e in qualche modo dal numero di stati per sapere se la corsa utilizza le celle infinite del nastro. Tuttavia, non sono sicuro di come posso usare il numero di stati e ciò che dovrei controllare. Ciò che mi confonde è che entrare in un ciclo infinito non richiede necessariamente l'uso di celle infinite del film.

$ l_k={ |\, M \, \, \, è \, \, a \, \, tm \, \, \, tm \, \, \, \, usi \, \, at \, \, la maggior parte \, \, k \, \, nastro\, \, celle \, \, \, when \, \, \, in esecuzione \, \, \, on \, \, \, \ esilon \ \ \, \, \ esilon \ \} $

Dimostrare che: $ l ^ *=BIGCUP \ LIMITS_ {K \, \ in \, \ mathbb {n}} l_k \, \ in \, \, \, re \ setminus r $

Answer 1

la lingua $ l ^ * $ consiste in tutte le macchine Turing $ m $ che alla fine si fermanoo ripetere una configurazione.Per ogni macchina $ m $ , simulando la macchina che è possibile osservare facilmente quella di queste possibilità è successo.