Computability Theory

Editorial

Material in this chapter should be reviewed and expanded. In particular, there are no exercises yet.

Kleene normal form theorem

[Kleene's Normal Form Theorem] There is a primitive recursive relation $T(e, x, s)$source and a primitive recursive function $U(s)$source, with the following property: if $f$source is any partial computable function, then for some $e$source,

for every $x$source.

Proof

[Proof Sketch] For any model of computation one can rigorously define a description of the computable function $f$source and code such description using a natural number $e$source. One can also rigorously define a notion of “computation sequence” which records the process of computing the function with index $e$source for input $x$source. Such a computation sequence can likewise be coded as a number $s$source. This can be done in such a way that

1. the relation $T(e, x, s)$source, which holds iff a number $s$source codes the computation sequence of the function with index $e$source on input $x$source, and

2. the function $U(s)$source which maps a computation sequence coded by $s$source to the end result of that computation

are both computable. In fact, the relation $T$source and the function $U$source are primitive recursive.

Explain

In order to give a rigorous proof of the Normal Form Theorem, we would have to fix a model of computation and carry out the coding of descriptions of computable functions and of computation sequences in detail, and verify that the relation $T$source and function $U$source are primitive recursive. For most applications, it suffices that $T$source and $U$source are computable and that $U$source is total.

It is probably best to remember the proof of the normal form theorem in slogan form: $\umin{s}{T(e, x, s)}$source searches for a computation sequence of the function with index $e$source on input $x$source, and $U$source returns the output of the computation sequence if one can be found.

Infinitely many indices theorem

Every partial computable function has infinitely many indices.

Explain

The next theorem is known as the “$s$source-$m$source-$n$source theorem,” for a reason that will be clear in a moment. The hard part is understanding just what the theorem says; once you understand the statement, it will seem fairly obvious.

Parameterization theorem

For each pair of natural numbers $n$source and $m$source, there is a primitive recursive function $s^m_n$source such that for every sequence $e$source, $a_0$source, dots, $a_{m-1}$source, $y_0$source ,dots, $y_{n-1}$source, we have

Explain

It is helpful to think of $s^m_n$source as acting on programs. That is, $s^m_n$source takes a program $e$source for an $(m+n)$source-ary function, as well as fixed inputs $a_0$source, dots, $a_{m-1}$source; and it returns a program $s^m_n(e, a_0, \dots, a_{m-1})$source for the $n$source-ary function of the remaining arguments. It you think of $e$source as the description of a Turing machine, then $s^m_n(e, a_0, \dots, a_{m-1})$source is the Turing machine that, on input $y_0$source, dots, $y_{n-1}$source, prepends $a_0$source, dots, $a_{m-1}$source to the input string, and runs $e$source. Each $s^m_n$source is then just a primitive recursive function that finds a code for the appropriate Turing machine.

Universal partial computable function theorem

There is a universal partial computable function $\fn{Un}(e,x)$source. In other words, there is a function $\fn{Un}(e,x)$source such that:

1. $\fn{Un}(e,x)$source is partial computable.

2. If $f(x)$source is any partial computable function, then there is a natural number $e$source such that $f(x) \simeq \fn{Un}(e,x)$source for every $x$source.

Proof

Let $\fn{Un}(e,x) \simeq U(\umin{s}{T(e,x,s)})$source, where $U$source and $T$source are as in Kleene's normal form theorem (Universal function proof reference to normal form).

Explain

This is just a precise way of saying that we have an effective enumeration of the partial computable functions; the idea is that if we write $f_e$source for the function defined by $f_e(x) = \fn{Un}(e,x)$source, then the sequence $f_0$source, $f_1$source, $f_2$source, dots includes all the partial computable functions, with the property that $f_e(x)$source can be computed “uniformly” in $e$source and $x$source. For simplicity, we are using a binary function that is universal for unary functions, but by coding sequences of numbers we can easily generalize this to more arguments. For example, note that if $f(x,y,z)$source is a $3$source-place partial recursive function, then the function $g(x) \simeq f((x)_0, (x)_1, (x)_2)$source is a unary recursive function.

No universal total computable function theorem

There is no universal computable function. In other words, any function $\fn{Un}'(k, x)$source which is such that if $f(x)$source is a total computable function, then there is a natural number $k$source such that $f(x) = \fn{Un}'(k,x)$source for every $x$source, is not computable.

Proof

The proof is a simple diagonalization: if $\fn{Un}'(k,x)$source were total and computable, then

would also be total and computable. However, by definition, $d(k)$source is not equal to $\fn{Un}'(k,k)$source. Hence, for every $k$source, the values of $d(x)$source and $\fn{Un}'(k, x)$source differ for at least one $x$source, namely $x = k$source.

Explain

Diagonalization explanation reference to universality above shows that we can get around this diagonalization argument, but only at the expense of allowing the universal function to be partial. That is, $\fn{Un}$source is universal for the total computable functions, it just isn't total. The diagonalization argument doesn't work in the partial case.

Partial diagonalization exercise

To understand why the diagonalization argument in the proof of Partial diagonalization exercise reference does not work in the partial case, consider the function $f(x) \simeq \fn{Un}(x,x)+1$source. Is it partial computable? If so, it has an index $e$source, i.e., $f(x) \simeq \fn{Un}(e,x)$source. What can you say about $f(e)$source?

Halting function theorem

Let

Then $h$source is not computable.

Proof

Suppose $h$source is computable. We show that this would let us define a universal computable function. Define

But now $\fn{Un'}(e, x)$source is a total function, and is computable if $h$source is. For instance, we could define $g$source using primitive recursion, by

then

Since $\fn{Un'}(e,x)$source agrees with $\fn{Un}(e,x)$source wherever the latter is defined, $\fn{Un'}$source is universal for those partial computable functions that happen to be total. But this contradicts Halting proof contradiction reference.

Proof

Suppose $h(e,x)$source were computable. Define the function $g$source by

The function $g$source is partial computable. For example, one can define it as $\umin{y}{h(x,x) = 0}$source. So, for some $e$source, $g(x) \simeq \fn{Un}(e, x)$source for every $x$source. Is $g$source defined at $e$source? If it is, then, by the definition of $g$source, $h(e,e) = 0$source ($h$source can only take the value $0$source if it is defined). By the definition of $h$source, this means that $\fn{Un}(e, e)$source is undefined. By our assumption that $g(x) \simeq \fn{Un}(e, x)$source for every $x$source, we have that $g(e)$source is undefined, a contradiction. On the other hand, if $g(e)$source is undefined, then $h(e,e) \neq 0$source, and so $h(e,e) = 1$source. It follows that $\fn{Un}(e, e)$source is defined. But since $g(x) \simeq \fn{Un}(e, x)$source, then $g(e)$source would also be defined. Again, a contradiction.

Explain

We can describe this argument in terms of Turing machines. Suppose there were a Turing machine $H$source that takes as input a description of a Turing machine $E$source and an input $x$source, and decides whether or not $E$source halts on input $x$source. Then we could build another Turing machine $G$source which takes a single input $x$source, runs $H$source to decide if the machine $M_x$source with index $x$source halts on input $x$source, and does the opposite. In other words, if $H$source reports that $M_x$source halts on input $x$source, $G$source goes into an infinite loop, and if $H$source reports that $M_x$source doesn't halt on input $x$source, then $G$source just halts. Does $G$source halt on its own index as input? The argument above shows that it does if and only if it doesn't---a contradiction. So our supposition that there is a such Turing machine $H$source must be false.

Definition of computable sets and relations

Let $S$source be a set of natural numbers. Then $S$source is computable iff its characteristic function $\Char{S}$source is. In other words, $S$source is computable iff the function

is computable. Similarly, a relation $R(x_0, \dots, x_{k-1})$source is computable if and only if its characteristic function is.

Computable sets and relations are also called decidable.

Explain

Notice that we now have a number of notions of computability: for partial functions, for functions, and for sets. Do not get them confused! The Turing machine computing a partial function returns the output of the function, for input values at which the function is defined; the Turing machine computing a set returns either $1$source or $0$source, after deciding whether or not the input value is in the set or not.

Definition of computably enumerable sets

A set is computably enumerable if it is empty or the range of a computable function.

History

Computably enumerable sets are also called recursively enumerable instead. This is the original terminology, and today both are commonly used, as well as the abbreviations “c.e.” and “r.e.”

Explain

You should think about what the definition means, and why the terminology is appropriate. The idea is that if $S$source is the range of the computable function $f$source, then

and so $f$source can be seen as “enumerating” the elements of $S$source. Note that according to the definition, $f$source need not be an increasing function, i.e., the enumeration need not be in increasing order. In fact, $f$source need not even be injective, i.e., repetitions in the enumeration $f(0)$source, $f(1)$source, $f(2)$source, dots of $S$source are allowed. For instance, the constant function $f(x) = 0$source enumerates the set $\{ 0 \}$source.

Equivalent definitions of computably enumerable sets theorem

Let $S$source be a set of natural numbers. Then the following are equivalent:

1. $S$source is computably enumerable.

2. $S$source is the range of a partial computable function.

3. $S$source is empty or the range of a primitive recursive function.

4. $S$source is the domain of a partial computable function.

Explain

The first three clauses say that we can equivalently take any non-empty computably enumerable set to be enumerated by either a computable function, a partial computable function, or a primitive recursive function. The fourth clause tells us that if $S$source is computably enumerable, then for some index $e$source,

In other words, $S$source is the set of inputs on for which the computation of $\cfind{e}$source halts. For that reason, computably enumerable sets are sometimes called semi-decidable: if a number is in the set, you eventually get a “yes,” but if it isn't, you never get a “no”!

Proof

Since every primitive recursive function is computable and every computable function is partial computable, Primitive range clause implication source implies Primitive range implication destination and Partial range implication source implies Partial range implication destination. (Note that if $S$source is empty, $S$source is the range of the partial computable function that is nowhere defined.) If we show that Primitive range return implication source implies Primitive range return implication destination, we will have shown the first three clauses equivalent.

So, suppose $S$source is the range of the partial computable function $\cfind{e}$source. If $S$source is empty, we are done. Otherwise, let $a$source be any element of $S$source. By Kleene's normal form theorem, we can write

In particular, $\cfind{e}(x) \fdefined$source and $= y$source if and only if there is an $s$source such that $T(e, x, s)$source and $U(s) = y$source. Define $f(z)$source by

Then $f$source is primitive recursive, because $T$source and $U$source are. Expressed in terms of Turing machines, if $z$source codes a pair $\tuple{(z)_0, (z)_1}$source such that $(z)_1$source is a halting computation of machine $M_e$source on input $(z)_0$source, then $f$source returns the output of the computation; otherwise, it returns $a$source.

We need to show that $S$source is the range of $f$source, i.e., for any natural number $y$source, $y \in S$source if and only if it is in the range of $f$source. In the forwards direction, suppose $y \in S$source. Then $y$source is in the range of $\cfind{e}$source, so for some $x$source and $s$source, $T(e,x,s)$source holds and $U(s) = y$source. But then $y = f(\tuple{x,s})$source. Conversely, suppose $y$source is in the range of $f$source. Then either $y = a$source, or for some $z$source, $T(e,(z)_0,(z)_1)$source and $U((z)_1) = y$source. Since, in the latter case, $\cfind{e}((z)_0) \fdefined = y$source, either way, $y$source is in $S$source.

(The notation $\cfind{e}(x) \fdefined = y$source means “$\cfind{e}(x)$source is defined and equal to $y$source.” We could just as well use $\cfind{e}(x) = y$source, but the extra arrow is sometimes helpful in reminding us that we are dealing with a partial function.)

To finish up the proof of Equivalent definitions proof resumption reference, it suffices to show that Range and domain equivalence first clause reference and Range and domain equivalence second clause reference are equivalent. First, let us show that Range to domain implication source implies Range to domain implication destination. Suppose $S$source is the range of a computable function $f$source, i.e.,

Let

Then $g$source is a partial computable function, and $g(y)$source is defined if and only if for some $x$source, $f(x) = y$source. In other words, the domain of $g$source is the range of $f$source. Expressed in terms of Turing machines: given a Turing machine $F$source that enumerates the elements of $S$source, let $G$source be the Turing machine that semi-decides $S$source by searching through the outputs of $F$source to see if a given element is in the set, halts if it is and keeps searching forever if it isn't.

Finally, to show Domain to range implication source implies Domain to range implication destination, suppose that $S$source is the domain of the partial computable function $\cfind{e}$source, i.e.,

If $S$source is empty, we are done; otherwise, let $a$source be any element of $S$source. Define $f$source by

Then, as above, a number $x$source is in the range of $f$source if and only if $\cfind{e}(x) \fdefined$source, i.e., if and only if $x \in S$source. Expressed in terms of Turing machines: given a machine $M_e$source that semi-decides $S$source, enumerate the elements of $S$source by running through all possible Turing machine computations, and returning the inputs that correspond to halting computations.

Existential characterization theorem

A set $S$source is computably enumerable if and only if there is a computable relation $R(x,y)$source such that

Proof

In the forward direction, suppose $S$source is computably enumerable. Then for some $e$source, $S = W_e$source. For this value of $e$source we can write $S$source as

In the reverse direction, suppose $S = \Setabs{ x }{ \lexists[y][R(x, y)] }$source. Define $f$source by

Then $f$source is partial computable, and $S$source is the domain of $f$source.

Paired halting set theorem

Let $K_0$source be the set $\Setabs{\tuple{e, x}}{\cfind{e}(x) \fdefined}$source. Then $K_0$source is computably enumerable but not computable.

Proof

To see that $K_0$source is computably enumerable, note that it is the domain of the function $f$source defined by

For, if $\cfind{e}(x)$source is defined, $f(\tuple{e, x})$source finds a halting computation sequence; if $\cfind{e}(x)$source is undefined, so is $f(\tuple{e, x})$source; and if $z$source doesn't even code a pair, then $f(z)$source is also undefined.

The fact that $K_0$source is not computable is just the undecidability of the halting problem, Paired halting set undecidability reference.

Self halting set theorem

The self-halting set $K = \Setabs{e}{\cfind{e}(e) \fdefined}$source is c.e. but not decidable.

Proof

Suppose $K$source is decidable, i.e., its characteristic function $\Char{K}$source is computable. Let

Let $k$source be the index of $d$source, i.e., $d \simeq \cfind{k}$source. Then $d(k) \simeq \cfind{k}(k)$source. This contradicts the fact that $d(k) \fdefined$source iff $\cfind{k}(k) \fundefined$source, which follows from the definition of $d$source.

$K$source is the domain of $f(x) = \umin{y}{T(x,x,y)}$source and so is c.e.

Closure under union and intersection theorem

Suppose $A$source and $B$source are computably enumerable. Then so are $A \cap B$source and $A \cup B$source.

Proof

Closure proof characterization reference allows us to use various characterizations of the computably enumerable sets. By way of illustration, we will provide a few different proofs.

For the first proof, suppose $A$source is enumerated by a computable function $f$source, and $B$source is enumerated by a computable function $g$source. Let

Then $A \cup B$source is the domain of $h$source, and $A \cap B$source is the domain of $j$source.

For the second proof, suppose again that $A$source is enumerated by $f$source and $B$source is enumerated by $g$source. Let

Then $k$source enumerates $A \cup B$source; the idea is that $k$source just alternates between the enumerations offered by $f$source and $g$source. Enumerating $A \cap B$source is tricker. If $A \cap B$source is empty, it is trivially computably enumerable. Otherwise, let $c$source be any element of $A \cap B$source, and define $l$source by

In computational terms, $l$source runs through pairs of elements in the enumerations of $f$source and $g$source, and outputs every match it finds; otherwise, it just stalls by outputting $c$source.

For the last proof, suppose $A$source is the domain of the partial function $m(x)$source and $B$source is the domain of the partial function $n(x)$source. Then $A \cap B$source is the domain of the partial function $m(x) + n(x)$source.

Expressing $A \cup B$source as a set of halting values is more difficult, because one has to simulate $m$source and $n$source in parallel. Let $d$source be an index for $m$source and let $e$source be an index for $n$source; in other words, $m = \cfind{d}$source and $n = \cfind{e}$source. Then $A \cup B$source is the domain of the function

Complement characterization theorem

Let $A$source be any set of natural numbers. Then $A$source is computable if and only if both $A$source and $\Complement{A}$source are computably enumerable.

Proof

The forwards direction is easy: if $A$source is computable, then $\Complement{A}$source is computable as well ($\Char{A} = 1 \tsub \Char{\Complement{A}}$source), and so both are computably enumerable.

In the other direction, suppose $A$source and $\Complement{A}$source are both computably enumerable. Let $A$source be the domain of $\cfind{d}$source, and let $\Complement{A}$source be the domain of $\cfind{e}$source. Define $h$source by

In other words, on input $x$source, $h$source searches for either a halting computation of $\cfind{d}$source or a halting computation of $\cfind{e}$source. Now, if $x \in A$source, it will succeed in the first case, and if $x \in \Complement{A}$source, it will succeed in the second case. So, $h$source is a total computable function. But now we have that for every $x$source, $x \in A$source if and only if $T(d, x, h(x))$source, i.e., if $\cfind{d}$source is the one that is defined. Since $T(d, x, h(x))$source is a computable relation, $A$source is computable.

Explain

It is easier to understand what is going on in informal computational terms: to decide $A$source, on input $x$source search for halting computations of $\cfind{d}$source and $\cfind{e}$source. One of them is bound to halt; if it is $\cfind{d}$source, then $x$source is in $A$source, and otherwise, $x$source is in $\Complement{A}$source.

Complement of paired halting set corollary

$\Complement{K_0}$source is not computably enumerable.

Proof

We know that $K_0$source is computably enumerable, but not computable. If $\Complement{K_0}$source were computably enumerable, then $K_0$source would be computable by Complement corollary characterization reference, contradicting Complement corollary halting set reference.

Explain

We now know that there is at least one set, $K_0$source, that is computably enumerable but not computable. It should be clear that there are others. The method of reducibility provides a powerful method of showing that other sets have these properties, without constantly having to return to first principles.

Generally speaking, a “reduction” of a set $A$source to a set $B$source is a method of transforming answers to whether or not elements are in $B$source into answers as to whether or not elements are in $A$source. We will focus on a notion called “many-one reducibility,” but there are many other notions of reducibility available, with varying properties. Notions of reducibility are also central to the study of computational complexity, where efficiency issues have to be considered as well. For example, a set is said to be “NP-complete” if it is in NP and every NP problem can be reduced to it, using a notion of reduction that is similar to the one described below, only with the added requirement that the reduction can be computed in polynomial time.

We have already used the notion of reduction notion implicitly. Define the set $K$source by

i.e., $K = \Setabs{x}{x \in W_x}$source. Our proof that the halting problem in unsolvable (Reducibility introduction halting reference) shows most directly that $K$source is not computable. Recall that $K_0$source is the set

i.e., $K_0 = \Setabs{\tuple{e,x}}{x \in W_e}$source. It is easy to extend any proof of the uncomputability of $K$source to the uncomputability of $K_0$source: if $K_0$source were computable, we could decide whether or not an element $x$source is in $K$source simply by asking whether or not the pair $\tuple{x, x}$source is in $K_0$source. The function $f$source which maps $x$source to $\tuple{x, x}$source is an example of a reduction of $K$source to $K_0$source.

Definition of many one reducibility

Let $A$source and $B$source be sets of natural numbers. A computable function $f\colon \Nat \to \Nat$source is a many-one reduction of $A$source to $B$source iff, for every natural number $x$source,

If such a reduction $f$source exists, we say that $A$source is many-one reducible to $B$source, written $A \leq_m B$source. If $A$source is many-one reducible to $B$source and vice-versa, then $A$source and $B$source are said to be many-one equivalent, written $A \equiv_m B$source.

Digress

It is true, but by no means obvious, that one-one reducibility really is a stronger requirement than many-one reducibility. In other words, there are infinite sets $A$source and $B$source such that $A$source is many-one reducible to $B$source but not one-one reducible to $B$source.

Transitivity of many one reducibility proposition

If $A \leq_m B$source and $B \leq_m C$source, then $A \leq_m C$source.

Proof

Composing a reduction of $A$source to $B$source with a reduction of $B$source to $C$source yields a reduction of $A$source to $C$source.

Transitivity proof exercise

Prove Transitivity exercise proposition reference by showing that if $f$source and $g$source are many-one reductions of $A$source to $B$source and $B$source to $C$source, respectively, then $\comp{f}{g}$source is a many-one reduction of $A$source to $C$source.

Reduction preservation proposition

Let $A$source and $B$source be any sets, and suppose $A \leq_m B$source.

1. If $B$source is computably enumerable, so is $A$source.

2. If $B$source is computable, so is $A$source.

Proof

Let $f$source be a many-one reduction from $A$source to $B$source. For the first claim, just check that if $B$source is the domain of a partial function $g$source, then $A$source is the domain of $\comp{f}{g}$source:

For the second claim, remember that if $B$source is computable then $B$source and $\Complement{B}$source are computably enumerable (Reduction proof complement premise reference). It is not hard to check that $f$source is also a many-one reduction of $\Complement{A}$source to $\Complement{B}$source, so, by the first part of this proof, $A$source and $\Complement{A}$source are computably enumerable. So $A$source is computable as well by Reduction proof complement conclusion reference. (Alternatively, you can check that $\Char{A} = \comp{f}{\Char{B}}$source; so if $\Char{B}$source is computable, then so is $\Char{A}$source.)