7.1. Partially Computable Languages

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.


Partially computable languages

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.


The halting problem is partially computable

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

HALT = {(p, x) | φp(x)↓}

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.


Another problem that is partially computable but not computable

Now you have seen one problem, HALT, that is partially computable but not computable. Here is another one,

Y1 = {p | p is a program that accepts input 1}

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

Recursive enumerability

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.