0
$\begingroup$

Do two halting Turing machines accept the same language?

Proof that it is undecidable(credit to another user on this website: "Tom van der Zanden"):

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 "reduction from the Halting problem to the problem of detecting equality?" 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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – JMF9
    May 6, 2021 at 13:41
  • $\begingroup$ I don't think that you are explaining the proof or answering my questions, but rather just restating what is written above. $\endgroup$
    – JMF9
    May 6, 2021 at 13:43
  • $\begingroup$ Then, what are you asking? To me it seems you asked to explain the proof... $\endgroup$
    – nir shahar
    May 6, 2021 at 13:52
  • $\begingroup$ As I understand it, checking whether M' is empty only decides the problem of whether M halts on input x in |x| or less steps. This is different from the halting problem in general; for example, |x| is finite and of course determining if a machine halts in a finite number of steps is decidable. So what am i misunderstanding? $\endgroup$
    – JMF9
    May 6, 2021 at 13:57
  • $\begingroup$ Notice that we simulate $M$ on $w$, for $|x|$ steps. $x$ and $w$ here are different things! We can think of $w$ as a constant and think of $x$ as the input variable. Hence if the language is not empty, there is such an $x$, thus $M$ halts on $w$ within $|x|$ steps, and in particular it does halt. $\endgroup$
    – nir shahar
    May 6, 2021 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.