Comprobación de si la máquina de Turing pasa al menos k> 2 estados antes de aceptar una palabra

Question

$ l={\ langose M, K \ Rangle \ Mid \ existe w \ in l (m) \ texto {tal que $ M $ pasa al menos al menos $ k> 2 $ estados distintos antes de aceptar $ w $ \ span \} $

Intento pensar en la reducción para demostrar que este lenguaje no es ni ni núcleo. ¿Cómo abordar este problema?¿Hay alguna pista, o intuición?

Por lo general, verifique que el arroz se puede usar, pero la pregunta aquí no se trata del idioma mismo

Answer 1

claramente $ l $ es aceptable (simplemente simular $ m $ y realice un seguimiento del número de Distintos estados encontrados durante la simulación). Ahora demostramos que no es decidible.

Si $ l $ fueron decidibles, podrías resolver el problema de detención de la siguiente manera: Dado un TM $ t $ y una entrada $ x \ in \ sigma ^ * $ , construye un TM $ m $ que ignora su entrada, simula $ t $ con entrada $ x $ y, cuando se completa la simulación, acepta. Puede asegurarse de que, si $ m $ acepta, entonces también atraviesa al menos $ 3 $ estados distintos por solo la transición del estado inicial a otro estado (distinto) antes de comenzar la simulación de $ t $ .

Ahora compruebe si $ \ langle m, 3 \ rangle \ en l $ . Si la respuesta es afirmativa, entonces hay algunos $ w \ in \ sigma ^ * $ para el $ m (w) $ acepta, mostrando que $ t (x) $ se detiene. Si la respuesta es negativa, entonces $ m $ nunca se detiene, mostrando que $ t (x) $ no lo hace detenerse