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?
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".