title: Proof that the halting problem is NP-hard?
body: <p>In <a href="https://stackoverflow.com/questions/1857244/np-vs-np-complete-vs-np-hard/1857342#1857342">this answer</a> to a question about the definitions of NP, NP-hard, and NP-complete, Jason makes the claim that</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>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.</p>
  
  <p><strong>Is there a straightforward proof that the halting problem is NP-hard?</strong></p>