For reasonable numberings of Turing machines, the halting problem is NP-hard. For unreasonable numberings, it might not be.
-
-
For reasonable numberings, the halting problem is RE-complete (and hence hard for any subclass of RE) under polynomial-time reductions.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.