Teorema do arroz para a máquina de Turing com saída fixa

Question

Então eu deveria provar com a ajuda do teorema de arroz se a linguagem: $ l_ {5}={w \ in \ {0,1} ^ {*} | \ forall x \ in {0,1 \} ^ {*}, M_ {w} (w)= x \} $ é decidível.

Primeiro de tudo: Eu não entendo, por que podemos usar o teorema de arroz em primeiro lugar: se eu escolheram dois Turingmachines $ m_ {w} $ e $ m_ {w '} $ com $ w \ neq w' $ então eu teria $ m_ {w} (w)= m_ {w '} (w)= x $ . Mas isso levaria a $ w '$ não estar em $ l_ {5} $ e $ w \ in l_ {5} $ . Ou eu sou mal-entendido algo?

segundo: a solução diz que a linguagem $ l_ {5} $ é decidível como $ l_ {5}=FORTSET $ porque a saída é claramente determinada com uma entrada fixa. Mas por que isso é assim? Eu pensei que $ l_ {5} $ não está vazio porque há tm que saía x em sua própria entrada e há alguns que não.

Answer 1

uma palavra $ W $ pertence à $ l_5 $ se para todos $ x \ \ \ \ \ {0,1 \} ^ * $ é o caso que $ m_w (w)= x $ .Em particular, se $ w \ in l_5 $ então $ m_w (W)= 0 $ e $ m_w (W)= 1 $ , que não pode ser verdadeiro.Portanto, nenhuma palavra pertence à $ l_5 $ .