0

There are different versions of the Halting Problem:

1) $\{ P \mid\text{there exists $i$ such that $P$ halts on $i$} \}$,

2) $\{ (P,k) \mid \text{there are less than $k$ inputs that $P$ halts on} \}$,

3) $\{ (P,k) \mid \text{there are $k$ (or more) inputs that $P$ halts on} \}$, and

4) $\{ P \mid P \text{ halts on } 0 \}$.

(1) is the standard problem in most books I've read. The proof that (1) is recognizable is just: Run P on i and accept if P halts.

Can someone show me the proofs for the other 3 (assuming they are recognizable...)

zarathustra
  • 4,891
user137481
  • 2,605

1 Answers1

1

The proof for 3) is simple: enumerate all inputs $(w_i)_{i\in\mathbb N}$ and run $P$ on each of them, using the standard trick (run $1$ step of $w_1$, then $2$ steps on $w_1$ and $1$ step on $w_2$,...). As soon as $P$ halts on $k$ inputs, accept $(P,k)$. As a consequence, 2) is not recognizable: it if were, one could decide the language $\{(P,k)\mid P \text{ halts on exactly } k \text{ inputs}\}$, and then we could decide the language $\{(P,w) \mid P\text{ halts on input } w\}$, which is a standard version of the halting problem.

Recognizability of 4) is trivial, run $P$ on $0$ and see what happens.

The proof for 1) is not quite was you say: you don't have $i$, so that you can't run $P$ on $i$. But 1) is just the specialization of 3) with $k=1$.

zarathustra
  • 4,891
  • I made a mistake in defining (1). I actually meant to define (4). So, for (3), we are allowed to assume that we have an infinite number of machines (i.e. one for each natural number)? That's strange because for an NFA we could use the trick only if the number of branches was finite. Thanks! – user137481 Aug 11 '14 at 16:46
  • Well, imagining an infinite number of machines $M_i$ running $P(w_i)$ is a way to see this. You only have to explain in which order you run them for the proof to be rigorous (you can't run $M_1$ for an infinite amount of steps, then $M_2$, obviously. That's why one nests all the steps so that each $M_i$ does one more step at some point in time). – zarathustra Aug 11 '14 at 17:19
  • another way is to consider a 2-tape machine that uses one tape to compute and the other to store the state of the computation for each machine. Thanks! – user137481 Aug 12 '14 at 14:40
  • @user137481: The number of tapes doesn't matter (as long as it is finite, of course), what is important is to specify in which order the steps are done! – zarathustra Aug 12 '14 at 14:41
  • I came across another version called the TOTAL language which is defined as TOTAL = {P | P(x) halts on all inputs}. This language is supposed to be neither Turing-Recognizable nor Co-Recognizable. This means the standard technique of proving that TOTAL is undecidable and then proving that its complement is recognizable in order to prove that TOTAL is unrecognizable doesn't work. I've seen a proof that uses the recursion theorem but it's too complex. Is that the only way to prove that TOTAL and its complement are both unrecognizable or will the techniques you provided here be sufficient? – user137481 Aug 22 '14 at 01:53
  • @user137481 You should create a new thread for this question. This site's aim is to be a repository of question/answers for which one has a quick access. Your question-in-comment currently escapes the search engine, which is not a good thing for the community. If this question has not been answered before, I'll happily answer it in a new thread! – zarathustra Aug 22 '14 at 17:19
  • OK, I will. But not right now. I'd like to think about it a bit more first. Thanks! – user137481 Aug 22 '14 at 20:09