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!

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

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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