>the problem of determining whether a given program halts. But that is not the Halting problem Huh? That is indeed the halting problem. More formally "given so

>the problem of determining whether a given program halts. But that is not the Halting problem Huh? That is indeed the halting problem. More formally "given some turing machine H and an input x, decide whether H halts on x." But it is of course trivially semi-decidable. >determining whether a program halts or does not halt That is equivalent to the formulation mentioned above, since if we had a decider W for the halting problem then H(x) halts iff W(H, x) accepts and halts, and H(x) does not halt iff W(H, x) rejects and halts. I think your confusion stems from the fact that if we had a decider for the halting problem, then the halting problem would be in R. But the fact that the halting problem is undecidable (i.e. not in R) means it is in RE but not co-RE.