In computability theory, the recursion operation is very narrowly defined. Given a function f:Nk→N and a function g:Nk+2→N, recursion yields a function h:Nk+1→N defined by
- h(x,0)=f(x)
- h(x,n+1)=g(x,n,h(x,n)).
In short, h(x,n+1) is defined recursively in terms of h(x,n). It is then understood that this operation (together with composition and basic initial functions) suffices to capture all self-referential functions. Throw in unbounded minimization and you have all computable functions whatsoever. But what about the Fibonacci sequence, h(n+1)=h(n)+h(n-1)? This seems to require a form of recursion which is strictly stronger than the weak version just defined. How does one show that the Fibonacci Sequence is primitive recursive?
One solution is to define an intermediate sequence which we might call the “Fibonacci Table Sequence”. The (n-1)th term of the Fibonacci Table Sequence is intended to encode the list of the first n Fibonacci numbers:
- T(0) = < 1 >
- T(1) = < 1, 1 >
- T(2) = < 1, 1, 2 >
- T(3) = < 1, 1, 2, 3 >
- T(4) = < 1, 1, 2, 3, 5 >
- And so on.
Now, even though individual Fibonacci numbers are defined in terms of two previous Fibonacci numbers, elements of the Fibonacci Table Sequence are only defined in terms of one previous element, namely:
- For n>1, T(n) is obtained by taking the two rightmost entries of T(n-1), adding them together, and appending the result to T(n-1).
The coding of sequences can, of course, be carried out by means of the Fundamental Theorem of Arithmetic; the details are very standard computability theory material.
Here is a double-starred exercise for the reader. Let C(n)=3n+1 if n is odd, and let C(n)=n/2 if n is even; this is the Collatz transformation, of course. Recall the Collatz Conjecture, which states that if you take any initial positive integer and apply C repeatedly, you’ll eventually return to 1. (This conjecture is one of the most profound open problems in contemporary mathematics, btw.) Based on this conjecture, it makes sense to define
- L(n) = the number of times C must be applied to n in order to reach 1.
An alternative, self-referential definition of L is
- L(1)=0
- L(n)=L(C(n))+1.
Exercise: Prove that L is computable, by using a modified version of the “Fibonacci Tables” idea and invoking unbounded minimization just one time. (Note, this does not require assuming the Collatz Conjecture… if the conjecture is true, then L has domain N+, and if the conjecture is false, then L has a smaller domain)
FURTHER READING
Collatz Recursion
Church’s Thesis
How I visualize certain subfields of math