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:

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 ?

  • $\begingroup$ To show that INF is undecidable, you want to reduce HALT to INF, not the other way around. $\endgroup$ – Yuval Filmus Feb 24 '18 at 21:36
  • 1
    $\begingroup$ Moreover, you cannot reduce INF to HALT, since HALT is in $\Sigma_1^0$ whereas INF is $\Pi_2^0$-complete. $\endgroup$ – Yuval Filmus Feb 25 '18 at 14:08
  • $\begingroup$ ok that makes sense to me, thanks for taking the time $\endgroup$ – zython Feb 25 '18 at 14:09

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}$.

  • $\begingroup$ thank you for the answer, I have two questions: $\Pi^0_2$ means "all total functions described by turing-machines" ? and: also my approach (if only sketched out) with rice is not wrong is it ? $\endgroup$ – zython Feb 24 '18 at 22:27
  • $\begingroup$ The class $\Pi_2^0$ is explained in the Wikipedia article on the arithmetical hierarchy. $\endgroup$ – Yuval Filmus Feb 24 '18 at 22:57

Your Answer

