HALT is a problem that belongs to the complexity class RE (recursively enumerable), which is a class that contains the complexity class NP. NP: Problems with e

HALT is a problem that belongs to the complexity class RE (recursively enumerable), which is a class that contains the complexity class NP. NP: Problems with efficient verifiers — given a candidate solution, you can check correctness in polynomial time. RE: Problems with semi-algorithms — you can recognize “yes” instances by eventually halting, but you may run forever on “no” instances. I wouldn't consider it a categorical error.