Cannot understand reductions from the halting problem and its complement

Question

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!

Answer 1

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.