Proving esistenza di TM che accetta la lingua successiva
-
29-09-2020 - |
Domanda
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={
Dimostrare che: $ l ^ *=BIGCUP \ LIMITS_ {K \, \ in \, \ mathbb {n}} l_k \, \ in \, \, \, re \ setminus r $
Soluzione
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.