Lest you get the idea that all problems are partially computable, let's see one that is not partially computable.
Define
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.
We have seen that, for every language S,
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 x ∈ S, run U(x) and V(x) in parallel. Eventually, one of them must stop, since U(x) stops if x ∈ S and V(x) stops if x ∉ S.
If U(x) stops, say that x ∈ S. If V(x) stops, say that x ∉ S. ◊
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. ◊