Teorema do arroz para a máquina de Turing com saída fixa
-
29-09-2020 - |
Pergunta
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.
Solução
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