3.1.7 - diagonal_method
3.1.7
The Diagonal Method
Introduction
As we learned in the previous article, primitive recursion, combined with a theory of functions, is a powerful tool for generating extremely large numbers very efficiently. However, it in itself, will not be sufficient for our purposes. One drawback of primitive recursion, particularly in how we have defined it, is that it can only be applied to functions of a single variable. Although we can remedy this somewhat by generalizing the definition at least to all fixed arity arrays, it still doesn't quite give us what we need. The problem is that repeated applications of primitive recursion quickly hits a snag which must be overcome with a second, and in someways, even more powerful principle: The diagonal method. When primitive recursion and the diagonal method are combined, the sky is the limit, and the two concepts seem almost inexhaustible. For us that's a good thing, because it means we'll be in business creating larger and larger numbers for a very long time. I'll first explain how primitive recursion hits a brick wall, and then show how the diagonal method not only allows us to jump over this wall, but also a seeming infinity of walls after that!
Primitive Recursion Hits a Wall
Recall our example from the previous article. We originally began with the function f(n) = 2n, an innocuous function that with only three applications of primitive recursion produced a function so fast growing it was quickly going beyond what we could envision with power towers! We saw that with the first application of primitive recursion we obtained:
R(n) = 2n
With the second we obtained:
R2(n) = 2^(2^(2^(2^ ... ^(2^(2^2)) ... ))) w/n 2s
With the third conventional notation becomes useless. However we can define it precisely by saying that:
R3(0) = 1
&
R3(n) = R2(R3(n-1))
In plain language this says that the zeroth member of the sequence R3 is 1, and every other member is equal to a power tower of 2s with as many terms as the value of the previous member. In very short order this shoots off beyond anything we would encounter in ordinary experience. For example:
R3(1) = 2
R3(2) = 2^2 = 4
R3(3) = 2^(2^(2^2)) = 65,536
R3(4) = 2^(2^(2^(2^ ... ... ^(2^(2^(2^2))) ... ))) w/65,536 2s (inconceivably large!)
R3(5) = 2^(2^(2^(2^ ... ... ^(2^(2^(2^2))) ... ))) w/R3(4) 2s (Hopelessly incomprehensible!)
etc.
If these numbers already seem like overkill, brace yourself, because we're about to push this idea to the extreme! It may seem that we now have a HUGE sandbox to work in, and we should never really run out of numbers to explore, just with primitive recursion and the elementary functions, and to some extent this is true. However, if we don't merely want to explore every nook and cranny of primitive recursion, but are more interested in simply going as far with large numbers as we can, we quickly crash into the ceiling. How so?
Well imagine we were to continue beyond this. Sure we could chose a very large argument like a 100, and come up with R3(100), but this, and any other number we could reasonably write out using decimal numbers and the function R3 will quickly be transcended if we instead simply apply primitive recursion to R3. It should be obvious how we could continue this add infinitum... simply chose 1 as the base for each successive primitive recursion on the previous recursive function. In other words, let:
R4(0) = 1
R4(n) = R3(R4(n-1)) : n>0
&
R5(0) = 1
R5(n) = R4(R5(n-1)) : n>0
&
in general let
Rk(0) = 1
Rk(n) = Rk-1(Rk(n-1)) : n>0
So we can now easily talk about an arbitrary number of applications of primitive recursion to any function. Try to imagine what kind of function R100(n) is. This is so beyond ordinary concepts of large numbers, that common questions used to ascertain their size such as "how many digits does it have" or "how many terms are in the power tower" become virtually impossible to answer and the answer becomes virtually meaningless. If we we're perhaps only aiming to come up with large numbers larger than we've ever thought of before, we might be satisfied with this, but we want to try to push this idea to the limit. How far can we really go? Why stop here if we can keep going? For better or worse, that is the googologist's mantra.
############################################################################
############################################################################
18:19.32
18:56.66