Théorème de Riz pour Turing Machine avec sortie fixe

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 $ w \ in l_ {5} $ . Ou suis-je mal compris quelque chose?

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.

Answer 1

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 $ M_W (W)= 1 $ , qui ne peut pas être vrai.Donc, aucun mot n'appartient à $ l_5 $ .