¿Por qué es innecidible el siguiente idioma?

Question

Actualmente estoy aprendiendo para mis exámenes este semestre y traté de resolver algunos exámenes antiguos de los últimos años.

La pregunta es mostrar, que no es indecidible. $ l={w | t (m_w) \ neq \ vacioset \ land \ forall x \ in t (m_w): xx \ in t (m_w) \ land xxx \ notin t (M_W) \} $

Mostré que el idioma $ l '={w | T (M_W) \ NEQ \ STOPSSET \} $ no es decidible debido al teorema del arroz. Creé a las máquinas de Turing $ m_1 $ con $ t (m_1)=vacioset $ y $ m_2 $ con $ t (m_2)=sigma ^ * $ para mostrar que el idioma l 'no es trivial . (desde $ 1 \ en l $ y $ 2 \ Notin A $ . Sin pérdida de generalidad, asume aquellos Las máquinas tienen el Gödelindexes 1 y 2)

Mi problema ahora es que no sé manera de mostrar, que este resultado se transfiere al idioma L. Sé que el lenguaje L solo debe contener tales índices de Gödel, que para esos índices, los siguientes TM deben aceptar palabras infinitas ( porque en el caso de $ x \ in t (m_w) $ debe haber $ xx \ in t (m_w) $ < / span> ... y, por lo tanto, debe ser $ xxxx \ in t (m_w) $ etc.)

¡Me encantaría escuchar sugerencias / respuestas! Gracias de antemano

Answer 1

Esta es una consecuencia directa del teorema del arroz. Una palabra $ w $ está en $ l $ si $ T (M_W) $ satisface la siguiente propiedad semántica:

$ t (m_w) $ no está vacío, y para cualquier $ x \ in t (m_w) $ , tenemos $ x ^ 2 \ in t (m_w) $ y $ x ^ 3 \ Notin t (M_W) $ .

Para demostrar que este idioma no es decidible de acuerdo con el teorema de Rice, debemos exhibir dos máquinas de Turing $ w_1 $ y $ W_2 $ : uno que no satisface la propiedad, y otro que lo satisface. Podemos tomar $ W_1 $ para ser una máquina de tal manera que $ t (m_ {w_1})=vacioset $ , y $ w_2 $ para ser una máquina de tal manera que $ t (m_ {w_2})={a ^ {2 ^ n}: n \ geq 0 \} $ .