¿Puede alguien explicarme la prueba?

Question

No entiendo muy bien la prueba y no entiendo por qué es M2 el que "lleva" a un estado de rechazo en lugar de M1.

Answer 1

Así que $M_{1}$ y $M_{2}$ son máquinas de Turing tales que $L(M_{1}) = L_{1}$ y $L(M_{2}) = L_{2}$ . Desde $L_{1}, L_{2}$ son recursivamente enumerables, dada una cadena $\omega$ , si $\omega \in L_{i}$ entonces $M_{i}$ se detendrá y aceptará $\omega$ .

Así que la prueba es por simulación. Consideremos una máquina de Turing $M$ en la entrada $\omega$ . Simula $M_{1}$ y $M_{2}$ en $\omega$ simultáneamente. Si $M_{1}$ se detiene y acepta $\omega$ , $M$ acepta $\omega$ . Por lo demás, $\omega \in L_{2}$ Así que $M_{2}$ se detendrá y aceptará $\omega$ , lo que provocará $M$ para rechazar $\omega$ . Así que estamos decidiendo en qué conjunto $\omega$ pertenece.