Can someone explain me the proof?

51 Views Asked by At

enter image description here

I don't really understand the proof and I don't understand why it is M2 that "leads" to a reject state instead of M1.

1

There are 1 best solutions below

2
On

So $M_{1}$ and $M_{2}$ are Turing Machines such that $L(M_{1}) = L_{1}$ and $L(M_{2}) = L_{2}$. Since $L_{1}, L_{2}$ are recursively enumerable, given a string $\omega$, if $\omega \in L_{i}$, then $M_{i}$ will halt and accept $\omega$.

So the proof is by simulation. Consider a Turing Machine $M$ on input $\omega$. It simulates $M_{1}$ and $M_{2}$ on $\omega$ simultaneously. If $M_{1}$ halts and accepts $\omega$, $M$ accepts $\omega$. Otherwise, $\omega \in L_{2}$, so $M_{2}$ will halt and accept $\omega$, which will cause $M$ to reject $\omega$. So we are deciding in which set $\omega$ belongs.