10.5 Equivalence of Models

The previous section introduced several formal models of computation and stated that they compute the same class of functions. In this section, we give a more systematic account of this equivalence by presenting explicit constructions that translate computations from one model into another.

The central result is that all standard models define exactly the same class of partial functions:

This class is called the class of partial computable functions.

Strategy of Proof

To prove equivalence, it suffices to show that each model can simulate one fixed model, typically Turing machines. If every model can simulate Turing machines and can be simulated by Turing machines, then all models are equivalent.

Thus we prove:

every partial recursive function is Turing computable,

every Turing computable function is partial recursive,

lambda calculus is equivalent to Turing machines.

The proofs rely on encoding finite objects such as machine configurations and programs as natural numbers.

Coding Configurations

A Turing machine configuration consists of a finite state, a finite tape content, and a head position. Since only finitely many tape cells are nonblank, the entire configuration can be represented as a finite string.

We encode such strings as natural numbers using a standard pairing or sequence coding.

Lemma 10.47 (Encoding of Configurations)

There exists a primitive recursive coding of Turing machine configurations by natural numbers such that the following functions are primitive recursive:

the function that extracts the current state,

the function that extracts the symbol under the head,

the function that updates a configuration according to one transition step.

Proof

Encode a configuration as a tuple:

where $q$ is the current state, $L$ is the finite sequence of symbols to the left of the head, and $R$ is the finite sequence consisting of the symbol under the head followed by the symbols to the right.

Each of these components can be encoded as a natural number. The state $q$ is an integer in a finite set, so it is already a natural number. The sequences $L$ and $R$ are encoded using a standard sequence coding such as prime exponent coding.

The decoding functions that recover $q$, $L$, and $R$ are primitive recursive because they involve extracting components from a coded tuple.

The transition function of the Turing machine is finite, so it can be represented as a finite lookup table. Applying the transition function to a configuration requires reading the current state and symbol, selecting the appropriate rule, and updating the sequences $L$ and $R$ accordingly. Each of these operations can be implemented using primitive recursive functions.

Thus there is a primitive recursive function that maps a configuration code to the code of its successor configuration.

Turing Machines to Recursive Functions

We now show that every Turing computable function is partial recursive.

Theorem 10.48

Every Turing computable function is partial recursive.

Proof

Let $M$ be a Turing machine computing a partial function:

Encode the input $(x_1,\dots,x_n)$ as a natural number and form the initial configuration $C_0$ of the machine on that input. Using Lemma 10.47, define a primitive recursive function:

that returns the code of the next configuration from the configuration coded by $c$.

Define a primitive recursive function:

which gives the configuration after $t$ steps, by primitive recursion on $t$:

Now define a primitive recursive predicate:

which holds if and only if the configuration $\operatorname{step}(c,t)$ is halting.

The output of the computation is obtained by finding the least $t$ such that $H(c,t)$ holds. Define:

If the machine halts, this minimization finds the least halting time. If the machine does not halt, the search continues forever.

Finally, define a function that extracts the output from the halting configuration:

which is primitive recursive because it operates on the coded configuration.

Then:

where $c$ is the code of the initial configuration.

Thus $f$ is obtained by composition of primitive recursive functions and minimization, and is therefore partial recursive.

Recursive Functions to Turing Machines

We now show the converse direction.

Theorem 10.49

Every partial recursive function is Turing computable.

Proof

We prove the statement by induction on the construction of partial recursive functions.

The initial functions are Turing computable. A Turing machine can compute the zero function by writing $0$. It can compute the successor function by incrementing a number. It can compute projection functions by extracting components from a coded tuple.

Closure under composition is preserved. If $g$ and $h_1,\dots,h_k$ are computed by Turing machines, then a Turing machine can compute each $h_i$ on the input, store the results, and then compute $g$ on those results.

Closure under primitive recursion is preserved. Suppose:

A Turing machine can compute $f(\vec{x},y)$ by first computing $g(\vec{x})$, then iterating the machine for $h$ exactly $y$ times, using a counter to keep track of the number of iterations.

Closure under minimization is preserved. Suppose:

A Turing machine can compute $f(\vec{x})$ by searching:

and computing $g(\vec{x},y)$ at each step. If a value of $y$ is found such that $g(\vec{x},y)=0$, the machine halts and outputs $y$. If no such $y$ exists, the search never terminates, which correctly represents partiality.

Thus every partial recursive function is Turing computable.

Lambda Calculus and Turing Machines

We now relate lambda calculus to Turing machines.

Theorem 10.50

A function is lambda definable if and only if it is Turing computable.

Proof

First, suppose a function is lambda definable. A lambda term is a finite symbolic expression, and beta reduction is a mechanical rewriting rule. A Turing machine can simulate beta reduction by scanning the term, locating reducible expressions, and performing substitution. Therefore every lambda definable function is Turing computable.

Conversely, suppose a function is Turing computable. The computation of a Turing machine can be encoded as a sequence of configurations. Each configuration can be represented as a lambda term. The transition function of the machine can be encoded as a lambda term that maps one configuration to the next.

Using standard encodings of numbers, pairs, and sequences, lambda calculus can represent the entire computation. A lambda term can repeatedly apply the transition function until a halting configuration is reached, and then extract the output.

If the Turing machine halts, the lambda term reduces to the representation of the output. If the Turing machine does not halt, the reduction sequence does not terminate. Thus every Turing computable function is lambda definable.

Corollary 10.51

The following classes of functions are identical:

partial recursive functions,

Turing computable functions,

lambda definable functions.

Proof

This follows immediately from Theorems 10.48, 10.49, and 10.50.

Robustness of Computability

The equivalence of models shows that computability is robust. Small changes in the definition of a model do not change the class of computable functions.

For example, allowing a Turing machine to move its head in three directions instead of two, or allowing multiple tapes instead of one, or allowing random access memory, does not change the class of computable functions.

Lemma 10.52

Multi tape Turing machines compute the same class of functions as single tape Turing machines.

Proof

A single tape Turing machine can simulate a multi tape machine by dividing its tape into several tracks and encoding the contents of each tape together with the head positions. Each step of the multi tape machine can be simulated by a finite sequence of steps of the single tape machine.

Conversely, a multi tape machine can simulate a single tape machine directly. Therefore both models compute the same class of functions.

Lemma 10.53

Adding new basic instructions to a model does not increase its computational power, provided the new instructions are themselves computable in the original model.

Proof

If a model is extended by adding a new instruction that computes a function $g$, and if $g$ is already computable in the original model, then any computation using the new instruction can be simulated by replacing each use of the instruction with the corresponding computation of $g$ in the original model.

Thus the extended model does not compute any new functions.

Significance

The equivalence of models shows that the concept of computability is not tied to a particular formalism. Instead, it is an intrinsic mathematical notion that can be captured in many different ways.

This justifies the use of any convenient model when studying computability. Results proved in one model apply to all models, and therefore to the general notion of algorithmic computation.

This also supports the Church Turing thesis, since many independent attempts to formalize computation all lead to the same class of functions.