1
$\begingroup$

When I was going through the reductions from $HP$ and $\overline{HP}$ in this handout, I do not understand how everywhere the following claim is made: $$⟨M,x⟩ \in \overline{HP} ⇒ \text{M does not halt on x} ⇒ M′ \text{ does not accept any strings} ⇒ L(M′)\text{ is finite} ⇒ M′ \in L_5.$$ Why does $M$ not halting on $x$ imply that $M'$ does not accept any string at all?

My understanding initially was that $M'$ is a non-deterministic Turing machine that simultaneously runs $M$ on all possible inputs, but that doesn't seem right. Can someone please take a few examples, $(L_3, L_4, L_5$ if possible) and explain how the reductions are performed?

Also, I do not understand what $\tau(⟨M,x⟩) = ⟨M'⟩$ means.

I do understand how reductions are done after reading a few pages from Sipser. I still don't understand how they're done in the linked handout though. If anyone can even comment on what book uses the same notation or the reduction procedure as the handout, it would be of a lot help!

$\endgroup$
1
  • $\begingroup$ that $M'$ a non-deterministic machine seems to lack at least one word. $\endgroup$
    – greybeard
    Aug 31, 2020 at 10:27

1 Answer 1

0
$\begingroup$

The machine $M'$ ignores its input, and just simulates $M$ running on $x$. Hence:

  • If $M$ halts on $x$ then $M'$ halts on all inputs.
  • If $M$ doesn't halt on $x$ then $M'$ doesn't halt on any input.

The notation $\tau(\langle M,x \rangle) = M'$ is the definition of a reduction $\tau$ from $\overline{HP}$ to $L_5$. The input to the reduction is an instance of the halting problem, which is a pair consisting of a Turing machine $M$ and an output $x$, and the output is the Turing machine $M'$ described above.

$\endgroup$

Your Answer

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

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