In this section, we look at a larger class of languages than the computable languages.
Initially, this will appear quite strange. After all, why would you want to lump uncomputable languages with computable ones? The next section will shed a bit of light on the reason, and more light will open up when we get to NP-completeness.
Definition. If p is a program, define Wp = {x | φp(x)↓}.
That is, Wp is the set of all strings on which p halts.
Definition. Language S is partially computable if there exists a program p so that S = Wp.
Think of partial computability as the rather strange idea that a program says yes by stopping and says no by looping forever.
To show that a language S is partially computable, it suffices to produce a program that halts when its input is a member of S and loops forever when its input is not in S.
Recall that HALT is defined by
The following program partially computes HALT.
halts(p, x) Run program p on input x.
That's it! Notice that
φhalts(p, x)↓ | ⇔ | φp(x)↓ |
⇔ | (p, x) ∈ HALT. |
So Whalt = HALT.
Now you have seen one problem, HALT, that is partially computable but not computable. Here is another one,
Y1 is uncomputable by Rice's theorem.
To show that Y1 is partially computable, all you need to do is to write a program that stops on input programs that accept 1 and loops forever on input programs that do not accept 1. The following will do the job.
y1(p) 1. Run p on input 1. 2. If p answered yes then answer yes else loop forever
For reasons that Sipser discusses, partially computable languages are also called recursively enumerable, or r.e. languages.
I will only use the term partially computable.