Teorema del riso per la macchina di tentazione con uscita fissa

Question

Quindi avrei dovuto dimostrare con l'aiuto del teorema del riso se la lingua: $ l_ {5}={w \ in \ {0,1 \} ^ {*} | \ forall x \ in \ {0,1} \ \ \ {0,1}} M_ {w} (w)= x \} $ è decidabile.

Prima di tutto: non capisco, perché possiamo usare il teorema del riso in primo luogo: se avrei scelto due turingmachines $ m_ {w} $ e $ m_ {w '} $ con $ w \ neq w' $ allora otterrei $ m_ {w} (w)= m_ {w '} (w)= x $ . Ma questo porterà a $ w '$ non essere in $ l_ {5} $ e $ w \ in l_ {5} $ . O sto fraintendendo qualcosa?

Secondo: la soluzione dice, che la lingua $ l_ {5} $ è decidabile come $ l_ {5}=DEVUTENT $ Poiché l'uscita è chiaramente determinata con un ingresso fisso. Ma perché è così? Ho pensato che $ l_ {5} $ non è vuoto perché ci sono TM che output X sul proprio input e ce ne sono alcuni che non sono.

Answer 1

una parola $ W $ appartiene a $ l_5 $ se per tutti $ x \ in \ {0,1 \} ^ * $ È il caso che $ m_w (w)= x $ .In particolare, se $ w \ in l_5 $ quindi $ m_w (w)= 0 $ e $ m_w (w)= 1 $ , che non può essere vero.Quindi nessuna parola appartiene a $ l_5 $ .