Demostrando la existencia de TM que acepta el siguiente idioma.

Question

Tengo una idea de cómo abordar el problema, pero no estoy seguro de eso. Dada una máquina de Turing, puedo verificar cuántos estados tiene la máquina, y de alguna manera por el número de estados para saber si la ejecución usa células interminables de la cinta. Sin embargo, no estoy seguro de cómo puedo usar el número de estados y lo que debería verificar. Lo que me confunde es que entrar en un bucle sin fin no requiere necesariamente el uso de celdas sin fin de la película.

$ l_k={ |\, M \, \, A \, IS \, TM \, A \, IS, TM \, A \, That \, \, At \, \, At \, \, la mayoría \, \, k \, \, cinta\, \, CELLAS \, \, \, cuando \, \, \, ON \, \, \, ON \, \, \, \ Epsilon \} $

demuestra que: $ l ^ *=bigcup \ limits_ {k \, \ in \, \ mathbb {n}} l_k \, \ in \, \, \, re \ setminus R $

Answer 1

El idioma $ l ^ * $ consiste en todas las máquinas de Turing $ m $ que eventualmente se detieneno repetir una configuración.Para cada máquina $ m $ , simulando la máquina que puede observar fácilmente que una de estas posibilidades ha sucedido.