7.2. All Computable Languages Are Partially Computable

Partial computability and regular computability are not mutually exclusive. In fact,

Theorem. Every computable language is partially computable.

Proof. Suppose that C is a computable language. Here is a program V that partially computes C.

  V(x)
  If xC then
    stop and answer yes
  else
    loop forever
  end if

The test xC can be done because C is computable. ◊