# Title: What does self-reference have to do with recursion?

## A Simple Example

The following is a recursive definition for a function. Such a definition is similar to the common concept of a recurrence relation.

Consider a function f on the natural numbers such that:

f(0) = 1 and f(n+1) = 2*f(n)+1 for all natural numbers n.

Notice that we gave a definition for a function, but used the function itself in our definition.

For this example, in order to figure out what f(n+1) is, we need to first find out what f(n) is. As you know, this definition in fact does define a function and f satisfies f(n) = 2^(n+1)-1 for all natural numbers n. One could verify this claim by using mathematical induction.

## A General Form

Let a function of two variables G(x,y) defined on the natural numbers and a number c be given.

One can use G and c to recursively define a function f such that f(0) = c and f(n+1) = G(f(n), n) for all natural numbers n.

A more general form of recursive definition can be found here and is listed as the primitive recursion axiom.

## A Recursion Theorem

Recursive definitions as described above are self-referential definitions. But, it still isn't clear what self-referential programs such as quines have to do with recursion. Before describing their relationship, we need to first introduce a special (and equivalent) form of the recursion theorem.

Theorem: Let a total computable function of two variables G(x,y) defined on the natural numbers be given. There exists a source code e that computes a function E such that E(n) = G(e,n) for all natural numbers n.

Further, if G is not total computable, but only partial computable, then there exists e and E such that E(n) = G(e,n) for all n such that G(e,n) is defined.

We describe how to construct the source code e here.

The theorem has to do with self-referential programming because evaluating the function E is the same as evaluating G on the source code corresponding to E. Oddly, the theorem doesn't appear to have much to do with recursion, but we will see that it does.

## Recursion via Recursion Theorem

The following is the connection between self-referential programs and recursion.

The Connection: Recursively defined functions can be computed using the recursion theorem and a universal program.

A universal program is a program U that takes as input a source code x and a string y and then simulates x's program on input y.

The Construction: Let a total computable function of two variables G(x,y) defined on the natural numbers and a number c be given.

As mentioned above, we know that there exists a function f such that f(0) = c and f(n+1) = G(f(n), n) for all natural numbers n. We will proceed by describing how to compute f.

Consider a (partial) computable function of two variables H(x,y) such that H(x,0) = c and H(x, y+1) = G(U(x,y), y).

Now, we apply the recursion theorem to H to get E(n) = H(e,n). Therefore, we have E(0) = H(e,0) = c and E(n+1) = H(e, n+1) = G(U(e,n), n) = G(E(n), n).

One can show by mathematical induction that E is total computable and it follows that E is the function f that we were trying to compute. □

Go to: How do you make quines and self-referential programs?

Back to Programs