0

The version of the Halting Problem I'm familiar with is:

{ (P, i) : P halts on input i }

I've seen the following other versions mentioned:

1) { (P, i): there exists i such that P halts on i }
2) { (P, i): P halts on less that k inputs i }
3) { (P, i): P halts on more than k inputs i }

I've not seen any proofs for these versions. Can anyone show me the proofs?

user137481
  • 2,605

1 Answers1

1

What you mean is, I suppose

1) { $P$ | there exists $i$ such that $P$ halts on $i$ }

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

3) { $(P,k)$ | there are $k$ (or more) inputs that $P$ halts on }

and for good measure, let's throw in

4) { $P$ | $P$ halts on 0 }

Now suppose you have something that decides (1). You can use that to decide your canonical halting problem: Given $(P,i)$ construct the machine $Q$ that ignores its input and runs $P$ on $i$ instead. Run your (1)-decider on $Q$. Then $P$ halts on $i$ iff there is anything $Q$ halts on.

We can use exactly the same reduction to see that (4) is undecidable. For (3) we run the hypothesized (3)-solver on $(Q,1)$.

For (2), given $(P,i)$ construct the machine $R$ that computes $$ R(x) = \begin{cases} P(i) & \text{if }x=0 \\ \bot & \text{otherwise} \end{cases} $$ and ask your hypothetical (2)-solver whether there are less than 1 input that $R$ halts on. Then $P$ halts on $i$ iff the answer is "no".

hmakholm left over Monica
  • 286,031
  • what does the upside down T in your answer for (2) mean? And is (4) the standard halting problem? – user137481 Aug 10 '14 at 23:41
  • $\bot$ (pronounced "bottom") means "do not produce any result, enter an infinite loop instead". The most standard halting problem would either be your original or (4). Since they are equally undecidable people don't always care a lot whether they mean one or they other when they say "the" halting problem. – hmakholm left over Monica Aug 11 '14 at 04:01
  • Thanks! I'm going to be posting a follow up question that deals with the recognizability (i.e. recursive enumerable) of the different version. – user137481 Aug 11 '14 at 12:59