provando existência de tm que aceita a próxima língua

Question

Eu tenho uma ideia de como abordar o problema, mas não tenho certeza sobre isso. Dada uma máquina de Turing, posso verificar quantos estados a máquina tem, e de alguma forma pelo número de estados para saber se a corrida usa células infinitas da fita. No entanto, não tenho certeza de como posso usar o número de estados e o que eu deveria verificar. O que me confunde é que entrar em um loop sem fim não requer necessariamente o uso de células infinitas do filme.

$ l_k= { |\, M \, \, \, é \, \, a \, \, tm \, \, que \, \, usa \, \, \, \, \, a maioria \, k \, \, fita\, \, células \, \, \, quando \, \, \, em execução \, \, \, on \, \, \, \ epsilon} $

Prove que: $ l ^ *=bigcock \ limites_ {k \, \ in \, \ mathbb {n}} l_k \, \ in \, \, re \ setminus r $

Answer 1

a linguagem $ l ^ * $ consiste em todas as máquinas de Turing $ m $ que eventualmente parouou repetir uma configuração.Para cada máquina $ m $ , simulando a máquina, você pode observar facilmente que uma dessas possibilidades aconteceu.