7.3. Problems that Are Not Partially Computable

Lest you get the idea that all problems are partially computable, let's see one that is not partially computable.

Define

Q = {p | φp(x)↑ for every x}

So Q is the set of all programs that loop forever on every input.

Q is not partially computable. Proving that would take us too far out of the way, but you can imagine the difficulty.

If you want to write a partial decider for Q, you need to write a program Qdecider that can recognize programs p that loop forever on every input, and Qdecider needs to do that in a finite amount of time so that you can stop. (It says yes by halting.) We know that you cannot tell if p loops forever on even one input, let alone all of them.


Complementary problems

We have seen that, for every language S,

S is computable ⇔ S is computable.

Partial computability does not have a similar result. But

Theorem. S is computable ⇔ both S and S are partially computable.

Proof.

(⇒) Suppose that S is computable. Then S is also computable. But that means that S and S are both partially computable, since every computable language is also partially computable.

(⇐) Suppose that both S and S are partially computable. Choose a program U that partially decides S and another program V that partially decides S.

To decide whether xS, run U(x) and V(x) in parallel. Eventually, one of them must stop, since U(x) stops if xS and V(x) stops if xS.

If U(x) stops, say that xS. If V(x) stops, say that xS. ◊


More problems that are not partially computable

We know that HALT is partially computable. If HALT were also partially computable, then, by the above theorem, HALT would be computable (which it is not).

So HALT must not be partially computable. In fact, we easily get a corollary from the above theorem.

Corollary. If L is a language that is partially computable but not computable, then L is not partially computable. ◊