Teorema del arroz para la máquina de Turing con salida fija

Question

Así que se suponía que debía probar con la ayuda del teorema del arroz si el idioma: $ l_ {5}={w \ in \ {0,1 \ \ in \ {*} | \ forall x \ in \ {0,1 \} ^ {*}, M_ {w} (w)= x \} $ es decidible.

En primer lugar: no entiendo, por qué podemos usar el teorema de Rice en primer lugar: si eligiera dos mesas de trabajo $ m_ {w} $ y $ m_ {w '} $ con $ w \ neq w' $ entonces obtendría $ m_ {w} (w)= m_ {w '} (w)= x $ . Pero esto llevaría a $ w '$ no estar en $ l_ {5} $ y $ w \ in l_ {5} $ . ¿O estoy malentendido algo?

Segundo: la solución dice que el idioma $ l_ {5} $ es decidible como $ l_ {5}=STOPSET $ porque la salida se determina claramente con una entrada fija. Pero ¿por qué es así? Pensé que $ l_ {5} $ no está vacío porque hay TM que sale x en su propia entrada y hay algunos que no lo hacen.

Answer 1

Una palabra $ w $ pertenece a $ l_5 $ si para todos los $ x \ in \ {0,1 \} ^ * $ Es el caso de que $ M_W (W)= x $ .En particular, si $ w \ in l_5 $ luego $ m_w (w)= 0 $ y $ M_W (W)= 1 $ , que no pueden ser verdaderos.Así que ninguna palabra pertenece a $ l_5 $ .