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. □