Foundations of Complexity Lesson 2: Computable and Computably Enumerable Languages

In Lesson 1 we described the Turing machine model to answer the question, "What is a computer?" The next question is "What can we compute?" First we need some definitions to describe problems to be computed.

First we need an alphabet which we denote Σ. Any finite Σ would work; for most of complexity we assume that Σ = {0,1}. Machines take as inputs words or strings consisting of a finite sequence of alphabet symbols or characters. Examples: 0101, 000, 1101100. The length of the string is the number of characters in the string. We use ε to represent the special string with zero characters.

A language is set of strings. It could be finite or infinite. Examples include

• {ε,0,1,001}
• The set of strings of odd length
• {1,10,110,1110,11110,...}

We use Σ^* to represent the set of all strings and ∅ to represent the empty set of no elements. Note the difference between the empty set of strings and {ε}, the set consisting of the single string of length zero.

A class is a set of languages. Examples of classes include

• The class of all finite languages.
• The class of all languages containing the string ε.
• The class of all languages that are subsets of {0,1,00,11,101}.

A complexity class is a special kind of class based on resource-bounded Turing machines. We will come back to complexity classes in a later lesson.

Consider a Turing machine M on some input string x which we denote M(x). We will focus on two possible outputs "yes" or "no". This yields three possibilities for M(x).

1. M(x) outputs "yes" in which case we say M(x) accepts.
2. M(x) outputs "no" in which case we say M(x) rejects.
3. M(x) does not halt.

We let L(M) be the set of strings x such that the first case occurs. A machine M such that the third case does not occur for any x is called total.

The class of computably enumerable languages is the set of languages L such that L = L(M) for some Turing machine M. You might see recognizable or recursively enumerable as other names for the computably enumerable languages.

The class of computable languages consists of the set of languages L such that L = L(M) for some total Turing machine M. You might see decidable or recursive as other names for the computable languages.