> (much like NP-Complete problems are a subset of Complete problems)
That sentence is messed up in a bunch of ways. You probably meant: "Turing-undecidable problems are a subset of NP-hard problems."
That sentence is messed up in a bunch of ways. You probably meant: "Turing-undecidable problems are a subset of NP-hard problems."
(Actually, are uncomputable problems necessarily NP-hard? This sounds obvious at first, but then you realize, wait, why would the reduction be polynomial time? If we assume our undecidable problem is at least as hard as the halting problem there's an obvious constant-time reduction, but what if it's intermediate? Is this something that's known?)
You're right to raise that question. It's a classical result of computability theory that there exists an undecidable problem that is strictly easier than the halting problem: http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_...