Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?" Do two halting Turing machines accept the same language?
Proof that it is undecidable(credit to another user on this website: &quot;Tom van der Zanden&quot;):
Let M be an arbitrary Turing machine. Let M′ be a Turing machine that on input x, simulates M (on some predefined input) for |x| steps and accepts if (and only if) M halts within |x| steps. If M doesn't halt then M′ accepts the empty language. If M does halt then the language M′ accepts is non-empty. This gives a reduction from the Halting problem to the problem of detecting equality, since we just need to ask whether M′ is equal to the machine accepting the empty language.
How is this proof using &quot;reduction from the Halting problem to the problem of detecting equality?&quot; Asking whether a TM halts in a finite number of steps (|x| in the proof above) is decidable. So how would the problem of detecting equality outlined above provide a way of solving the halting problem?
In other words my problem with understanding the proof is this: How does detecting equality in the way described above decide whether the machine M halts on input x?
Let $\langle M, w\rangle$ be the input to the halting problem.
We will construct $M'$ that simulates $M$ as you described with $w$ as the predefined input.
As you have said, $L(M')\neq \emptyset\iff M \text{ halts}$. However, we simulated $M$ on $w$, hence $L(M')\neq \emptyset \iff M \text{ halts on } w \iff \langle M, w\rangle\in H_{TM}$ where $H_{TM}$ is the halting problem.
Define the function $f$ that given $\langle M, w\rangle$ will output $\langle M', M_{empty}\rangle$, where $M_{empty}$ is a TM that immediately rejects.
We will have: $\langle M, w\rangle \notin H_{TM} \iff L(M')= \emptyset \iff L(M')\neq L(M_{empty})\iff \langle M', M_{empty}\rangle\in EQ_{TM}$
$f$ is computable, and hence it is a reduction from $\overline H_{TM}$ to $EQ_{TM}$.
$\overline H_{TM}$ is not decidable, and thus also $EQ_{TM}$ isn't decidable