Por que a linguagem seguinte é indecidável?

Question

Atualmente estou aprendendo para os meus exames neste semestre e tentei resolver alguns antigos exames dos últimos anos.

A questão é mostrar, que eu não é indecidível. $ l={w | t (m_w) \ neq \ neq \ land \ forall x \ in t (m_w): xx \ in t (m_w) \ terra xxx \ notin t (M_w) \} $

Eu mostrei que a linguagem $ l '={w | T (m_w) \ neq \ vazio \} $ é indecidável devido ao teorema de arroz. Eu criei para Turing Machines $ m_1 $ com $ t (m_1)=FORTSET $ e $ m_2 $ com $ t (m_2)=sigma ^ * $ para mostrar que o idioma não é trivial . (Desde a $ 1 \ em l $ e $ 2 \ notin A $ . Sem perda de generalidade eu assumo aqueles máquinas têm os gödelindexes 1 e 2)

Meu problema agora é que eu não conheço nenhuma maneira de mostrar, que este resultado transfere para a linguagem L. Eu sei que a linguagem só deve conter esses índices de Gödel, que para esses índices o seguinte TM deve aceitar palavras infinitas ( porque no caso de $ x \ in t (m_w) $ deve haver $ xx \ em t (m_w) $ < / span> ... e, portanto, deve ser $ xxxx \ em t (m_w) $ etc.)

Eu adoraria ouvir sugestões / respostas! Agradecemos antecipadamente

Answer 1

Esta é uma conseqüência direta do teorema do arroz. Uma palavra $ W $ está em $ l $ se $ T (m_w) $ satisfaz a seguinte propriedade semântica:

.

$ t (m_w) $ não é vazio, e para qualquer $ x \ in t (m_w) $ , temos $ x ^ 2 \ in t (m_w) $ e $ x ^ 3 \ notin t (M_w) $ .

Para mostrar que esta linguagem é indecida de acordo com o teorema de Rice, precisamos exibir duas máquinas Turing $ w_1 $ e $ w_2 $ : um que não satisfaz a propriedade, e outro que satisfaz. Podemos tomar $ w_1 $ para ser alguma máquina, tal que $ t (m_ {w_1})=FORTSET $ , e $ w_2 $ para ser alguma máquina tal que $ t (m_ {w_2})={w_2})={w_2})={} {2 ^ n}: n \ geq 0 \} $ .