Non recursively enumerable language proof by reduction to non-HP

Question

I am trying to understand how the reduction proof for non r.e. languages works by following the examples from this website. In most cases to prove that a language is not r.e., you can reduce the language to the non halting problem which is not r.e.

For example, if I have

$$L_2 = \{\langle M\rangle\mid M \text{ is a TM and }|L(M)|\leq 3\}\,.$$

I construct $\tau(\langle M, x\rangle) = \langle M'\rangle$ such that $M'$ on input $w$: it erases its input, copies $M$ and $x$ to its tape, and runs $M$ on $x$; it accepts if $M$ halts on $x$. Then I prove the reduction is valid (see website)

But then if I have the language

$$L_4 = \{\langle M\rangle\mid M\text{ is a TM that accepts all even numbers}\}\,,$$

I construct $\tau (\langle M, x\rangle) = \langle M'\rangle$ such that $M'$ on input $w$: it runs $M$ on $x$ for $|w|$ steps; it rejects if $M$ halts on $x$ within $|w|$ steps, and accepts otherwise.

I know this may sound like a stupid question but beginnings are always hard until you understand the main logic behind it but why does $M'$ need to reject when $M$ halts? Why not accept when $M$ halts like in the first case?

Answer 1

From a programming perspective, a reduction argument is often like this: "If you have a subroutine that can effectively solve problem A, here's how you can use it to solve problem B. But problem B is unsolvable, therefore no such effective subroutine exists."

In your case, the non-halting problem (Is my input $\langle M, w\rangle$ a Turing machine and a word that makes it loop forever?) is not recursively enumerable. If we can make it recursively enumerable by adding an effective subroutine for problem B, then no such subroutine for problem B exists.

---

The language $L_2$ of Turing machines that accept three or fewer strings is not r.e. If it were, then there's a subroutine B which recognizes whether a TM accepts three or fewer strings. So: imagine a program that takes in a machine $M$ and a word $w$. The program makes a new machine $M^\prime$ which ignores its input and simulates $M$ on $w$. If the simulation finishes, $M^\prime$ accepts; otherwise it loops forever. So, $M^\prime$ accepts all inputs if $M$ halts on input $w$. $M^\prime$ doesn't accept any strings if $M$ loops forever on input $w$.

Our program makes $M^\prime$, then asks B whether $M^\prime$ accepts 3 or fewer strings. If it does, $M$ must loop forever on input $w$. We should accept ("LOOPS FOREVER"). Otherwise, we don't ("DOESN'T LOOP FOREVER").

Because our program solves an unsolvable problem with help from B, such a subroutine B cannot exist.

---

The language $L_4$ of Turing machines that accept all even numbers is not r.e. If it were, then there's a subroutine C which recognizes whether a TM accepts all even numbers. So, imagine we have a program that takes in a machine $M$ and a word $w$. The program makes a new machine $M^\prime$. On input $x$, the machine simulates $M$ on $w$ for $|x|$ steps, then rejects if $M$ has finished by then; otherwise it accepts. So, $M^\prime$ uses its input as a timer: it rejects all strings that are longer than the number of steps $M$ takes to halt on $w$. (If $M$ never halts, $M^\prime$ accepts all strings. If $M$ halts, $M^\prime$ accepts all short strings and rejects all long strings.) So if $M$ never halts, $M^\prime$ accepts all strings, specifically including all even numbers. If $M$ halts, $M^\prime$ rejects all long strings, specifically including all large even numbers.

So, our program constructs $M^\prime$ and asks C whether it accepts all even numbers. If C says yes, it means that $M^\prime$ accepts all strings because $M$ loops forever on $w$. We accept ("LOOPS FOREVER"). If C says no, it means that $M$ eventually halts on input $w$. We reject ("DOESN'T LOOP FOREVER").

---

In both cases, $M^\prime$ uses "accept" to mean "LOOPS FOREVER", and "reject" to mean "DOESN'T LOOP FOREVER". In the first case, we made $M^\prime$ accept all strings when $M$ doesn't loop forever. In the second case, we made $M^\prime$ accept all strings when $M$ does loop forever. Those differences contributed to the discrepancy.