How to reduce $\{w \mid |T(M_w)| \geq 42\}$ to the halting problem?

Question

For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$.

I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I can't find a way to define an algorithm that halts only if $w \in L$. Either way:

• if $w \in L$ I would have to find at least 42 words that are in $T(M_w)$, which might be undecidable for certain languages.
• if $w \notin L$ then $M_w$ would accept only 41 or less words. Then we do know, that the language $T(M_w)$ is regular, but still we can't test if the language is regular or not.

Simply trying random words until we have at least 42 doesn't work as for some words the TM will not halt.

Is there any idea I could try? Or in other words: how would one prove $L \leq H_0 $?

Answer 1

This answer assumes that $T(w)$ is the set of inputs that the Turing machine $M_w$ halts on.

Given a Turing machine $M$, construct a new Turing machine which runs $M$ in parallel on all inputs. Once $M$ has halted on 42 different inputs, halt. (If this never happens, the new machine will never halt.)

In order to run $M$ on infinitely many inputs, you do the following:

• Start with some enumeration $x_1,x_2,\ldots$ of all inputs.
• Run $M$ for one step on $x_1$.
• Run $M$ for one step on $x_1,x_2$.
• Run $M$ for one step on $x_1,x_2,x_3$.
• And so on.

This is known as dovetailing.

The argument above reduces $L$ to the halting problem, and so shows that $L$ is r.e. We can also reduce the halting problem to $L$, hence showing that $L$ is r.e.-complete. To do this, suppose that we are given a Turing machine $M$ as input to $H_0$. We construct a new Turing machine which:

• On input $\epsilon$, transfers control to $M$.
• On input $0,00,\ldots,0^{41}$, halts.
• On all other inputs, doesn't halt.

The new machine belongs to $L$ iff the original one belongs to $H_0$.