Foundations of Complexity Lesson 4: Noncomputable Computably Enumerable Languages

Previous Lesson | Next Lesson

In the last lesson we showed that the set

L_D = { <M> | Machine M does not accept input <M>} is not computably enumerable. In this lesson we show there are languages that are computably enumerable but not computable.

For a set A, let A be the complement of A, i.e., all of the strings of Σ^* not in A. If A is computable then A is also computable--at the end if we accepted then we reject and vice-versa. Note this does not work in general for computably enumerable; switching reject and accept does not affect whether a machine halts on a given input.

Now consider the set

L_A = { <M> | Machine M does accept input <M>} L_A is just L_D.

Note the L_A is computably enumerable as we can just simulate M on <M>. If L_A were computable then so would L_D which we know is not even computably enumerable. Thus we have L_A as our first example of a noncomputable computably enumerable set.

Besides languages we can also consider computable functions. Consider a Turing machine with an output tape. We can view it as computing a function f from Σ^* to Σ^* where the value of f is the contents of the output tape after the machine enters a specified halting state. We say a total function f is computable if there is such a Turing machine computing f. We can also consider partially computable functions where f(x) may not be defined for some inputs x. On these inputs the corresponding machine does not halt.

In the next lesson we will use computable functions to show that other languages are not computable or computably enumerable.