1
$\begingroup$

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 ?

$\endgroup$
  • $\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
3
$\begingroup$

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

$\endgroup$
  • $\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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.