Reducing the infinite language problem to halting problem

Question

Let: $INF = \{ w \in \Sigma^* | \quad |L(M_w)| = \infty \} $.

It is easy to show with Rices theorem that $INF$ is not decidable. ($INF$ is non-trivial because of $\emptyset$ and $\Sigma^*$).

How can you show this with a reduction onto the halting problem (for example)?

---

Here are my thoughts:

I had an idea of running the decider of $INF$ in its own input, but couldnt get very far.

Another idea that I just had was:

Construct a Turing machine TM M' that halts if the language is finite, and loops endlessly if it is infinite:

M'(w):
for i=0,1,...
    simulate M_w on w_i

Knowing the halting problem we cannot know if that turing machine will halt or not. We have supposedly reduced $HALT$ on $INF$. Is this correct ? (Since we take an instance of $HALT$

Can I get some feedback on my solutions ?

Answer 1

Your language is actually $\Pi_2^0$-complete, and in particular even harder than the halting problem.

We can show that $\mathrm{INF}$ is $\Pi_2^0$-hard by reduction from $\mathrm{TOT} = \{ w : L(M_w) = \Sigma^* \}$. Indeed, given a Turing machine $M$, we can construct a Turing machine $M'$ which on input $x$, simulates $M$ sequentially on all inputs $y \leq x$ (using lexicographic order). It is not hard to check that $M'$ halts on infinitely many inputs iff $M$ halts on all inputs.

To show that $\mathrm{INF}$ is in $\Pi_2^0$, notice that a machine $M$ halts on infinitely many inputs if and only if for all inputs $x$ there exists an input $y \geq x$ and a number $n$ such that $M$ halts on $y$ within $n$ steps. Since the last condition is decidable, it follows that $\mathrm{INF}$ is in $\Pi_2^0$.

To answer the question you are interested in, all you need to do is to find a reduction from the halting problem to $\mathrm{TOT}$.