In this answer to a question about the definitions of NP, NP-hard, and NP-complete, Jason makes the claim that
The halting problem is the classic NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a decision problem but it is not in NP. It is clear that any NP-complete problem can be reduced to this one.
While I agree that the halting problem is intuitively a much "harder" problem than anything in NP, I honestly cannot come up with a formal, mathematical proof that the halting problem is NP-hard. In particular, I cannot seem to find a polynomial-time many-to-one mapping from instances of every problem in NP (or at least, any known NP-complete problem) onto the halting problem.
Is there a straightforward proof that the halting problem is NP-hard?