## Title: What does self-reference have to do with recursion?## A Simple ExampleThe 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 FormLet 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 ## A Recursion TheoremRecursive 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.
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 TheoremThe following is the connection between self-referential programs and recursion.
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.
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. □ |