Théorème de Riz pour Turing Machine avec sortie fixe
-
29-09-2020 - |
Question
Je suis donc censé prouver avec l'aide du théorème de Rice si la langue: $ l_ {5}={w \ in \ {0,1 \} ^ {*} | \ forall x \ \ {0,1} ^ {*}, M_ {w} (w)= x \} $ est décidable.
Tout d'abord: je ne comprends pas, pourquoi nous pouvons utiliser le théorème de Riz en premier lieu: si je choisirais deux TuringMachines $ m_ {w} $ et $ m_ {w '} $ avec $ w \ neq w' $ alors je voudrais obtenir $ m_ {w} (w)= m_ {w '} (w)= x $ . Mais cela conduirait à $ w '$ ne pas être dans $ l_ {5} $ $ et
Deuxièmement: la solution indique que la langue $ l_ {5} $ est décrivable comme $ l_ {5}=videtyset $ car la sortie est clairement déterminée avec une entrée fixe. Mais pourquoi est-ce vrai? Je pensais que $ l_ {5} $ n'est pas vide car il y a tm que la sortie x sur sa propre entrée et qu'il n'y en a pas.
La solution
Un mot $ w $ appartient à $ l_5 $ si pour tous $ x \ \ \ \ \ {0,1 \} ^ * $ C'est le cas que $ m_w (w)= x $ .En particulier, si $ w \ in l_5 $ alors $ m_w (w)= 0 $ et