Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?

Question

An alternative way of deciding within a nondeterministic complexity class is to present a verifier-prover pair. To recall, let $\mathsf{L}$ be a language, and let $\mathsf{w}$ be a word. To decide whether $\mathsf{w} \in \mathsf{L}$:

• The prover, a magical machine, will immediately find a proof that $\mathsf{w} \in \mathsf{L}$ and send it to the verifier. If $\mathsf{w} \notin \mathsf{L}$, however, the proof will be a fake. (In this sense the prover is said to be malicious.)

• The verifier, a Turing machine (or an equivalent), having received the proof, will decide whether the proof is true.

Here, there is no time/space restriction for the verifier, meaning that our complexity class in concern is $\mathsf{RE}$.

It is well-known that $\mathsf{HALT}$, the halting problem, is in $\mathsf{RE}$. In a simple sense, the verifier-prover pair would look like this. Let $\mathsf{w}$ be the program concerned whether to halt:

• If $\mathsf{w} \in \mathsf{HALT}$, the prover will immediately know how many Turing machine iterations are needed for $\mathsf{w}$ to halt.

  • The verifier will run $\mathsf{w}$ for exactly that many Turing machine iterations, see that $\mathsf{w}$ actually halted, and accept.

• If $\mathsf{w} \notin \mathsf{HALT}$, the prover will immediately know that $\mathsf{w}$ wouldn't halt, and will send the verifier a random number.

  • The verifier will run $\mathsf{w}$ for exactly that many Turing machine iterations, see that $\mathsf{w}$ actually didn't halt, and reject.

But what about its complement, $\mathsf{\text{NOT-HALT}}$? It is well-known that it is not in $\mathsf{RE}$. As such, I presume it means there cannot be a working verifier-prover pair for $\mathsf{\text{NOT-HALT}}$. But which machine should I blame? I see several ways of interpreting this:

• There is no way of proving $\mathsf{w}$ wouldn't halt. It's the prover's fault.

• It is possible to prove that $\mathsf{w}$ wouldn't halt, but there is no way of deciding whether the proof is true. It's the verifier's fault.

Answer 1

It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate to prove that an arbitrary TM will run forever.

If $L$ is not recursively enumerable, then no machine can simultaneously:

1. Halt on every input $\langle w, c\rangle$ (a word and a proof that the word is in the language).
2. Always answer correctly whether $w\in L$.

If a convincing certificate $c(w)$ really did exist for every word $w$ in the language, and a verifier with these two properties existed, then the language would be recursively enumerable and here is the Turing machine to prove it:

M(x): on input x, iterate over every possible word $c$ in increasing order of length and run the verifier on $\langle x,c\rangle$. Halt and respond YES if the verifier ever accepts, otherwise keep iterating forever.

It's not the verifier's fault. If a language is not recursively enumerable, then (equivalently) it is algorithmically impossible to confirm membership in the language. In particular, no certificate can help.