Also I just realized that just because something is at least as hard as the halting problem, doesn't necessarily mean it stays so when you restrict to polynomia

Also I just realized that just because something is at least as hard as the halting problem, doesn't necessarily mean it stays so when you restrict to polynomial-time reductions. So maybe even what I stated above isn't true. :-/ Well, the halting problem is NP-hard, at any rate. :P