Read Part 1 if you haven't already.
Recursion is when a function has itself in its definition. This may seem impossible, as it would keep referencing itself forever and no result would ever be returned, as in the function
f(x) = f(x)+1.
This would be undefined for all values x:
f(x) = f(x) + 1 = (f(x)+1) + 1 = f(x) + 2 = (f(x)+1) + 2 = f(x) + 3 = ...
By repeatedly replacing f(x) with f(x) + 1, one can see that the sum just climbs to infinity. Therefore, this recursive function does not make sense. However, there are recursive functions that are well-defined, one of which is the factorial.
n factorial, written n!, is the product of all integers from 1 to n for positive integer values of n. For example, 5! = 1*2*3*4*5 = 120. The factorial can be defined recursively as follows:
n! = 1 if n = 0, and n*(n-1)! otherwise.
This definition says two things:
1. 0! = 1 - a surprising fact, but a logical way to start and "build up" the other factorials.
2. Every factorial of n where n > 1 is just n * the previous factorial.
This makes sense, as, for example, 4! = 1*2*3*4 = (1*2*3)*4 = 3!*4. Grouping together every number in the product except the last gives (n-1)!, and the number left is n.
Calculating 6! would be as follows:
6! = 6*5! = 6*(5*4!) = 6*5*(4*3!) = 6*5*4*(3*2!) = 6*5*4*3*(2*1!) = 6*5*4*3*2*1 = 720.
Recursive functions are only well-defined (for our purposes) if
a. A function f(x) doesn't have f(x), but f(x-1) or f(x-n) where n is some positive integer, in its definition.
b. It must include a stopping point, usually at x = 0.
Now, we are ready to define our function for hyperoperators.
The function f would accept three arguments - a (the first operand), h (the hyperoperator), and b (the second operand). For example, 2^4 would be written as f(2,3,4). The edge cases would be as follows:
f(a,h,b) = b+1 if h=0, because the zeroth operator is the successor function.
If b = 0, there are a few sub-cases that need to be considered:
If h = 1, f(a,1,0) = a+0 = a, so if b = 0 and h = 1, the function should return a.
If h = 2, f(a,2,0) = a*0 = 0, so if b = 0 and h = 2, it should return 0.
If h = 3, f(a,3,0) = a↑0 = 1, so if b = 0 and h = 3, it should return 1.
What if b = 0 and h > 3 - that is, what is a↑↑0, a↑↑↑0, etc.? To answer this, we need to remember why a↑0 = 1.
Start with powers of 2: 2↑1 = 2, 2↑2 = 4, 2↑3 = 8, etc. Every power of 2 is 2 times the last - that is, 2↑n = 2 * 2↑(n-1). Plugging in 1 for n, 2↑1 = 2*2↑0. Since 2↑1 = 2, 2=2*2↑0, and thus 2↑0 = 1. This holds for any number besides 2:
a↑n = a * a↑(n-1)
a↑1 = a * (a↑0)
a↑1 = a
a = a * (a↑0)
1 = a↑0
Let's extend this to tetration. 2↑↑1 = 2, 2↑↑2 = 4, 2↑↑3 = 16, 2↑↑4 = 65536, etc. Every number is 2 to the power of the last.
2↑↑n = 2↑(2↑↑(n-1))
2↑↑1 = 2↑(2↑↑0)
2 = 2↑(2↑↑0)
1 = 2↑↑0
Replace 2 with a and the proof holds. a↑↑0 = 1.
This can be further extended to any hyperoperator beyond tetration, so the last edge case would be:
If b = 0 and h > 2, f(a, h, b) = 1.
Now for the final case for the hyperoperator function, where neither b nor h are equal to 0. Since every hyperoperator is repeated application of the last,
f(a, h, b) = f(a, h-1, f(a, h-1, f(a, h-1, ... ) ... ), repeated b times. However, we can do better. Just like the factorial function grouped all numbers except the last, we can only put one "f(a, h-1," and then have the third argument be f(a, h-1, f(a, h-1, ... ) ... ), repeated b-1 times, which would be f(a, h, b-1). Now the last case has been solved:
If b ≠ 0 and h ≠ 0, f(a, h, b) = f(a, h-1, f(a, h, b-1)).
An example of this would be
2↑4 = f(2, 3, 4)
which, by this last case, is
f(2, 2, f(2, 3, 3)) = 2*2↑3
Using it on the inner function again, it becomes
f(2, 2, f(2, 2, f(2, 3, 2))) = 2*2*2↑2
and then
f(2, 2, f(2, 2, f(2, 2, f(2, 3, 1)))) = 2*2*2*2↑1.
It works! 2↑4 leads to multiplying 2 by itself 4 times! Now, the full hyperoperator function, which defines addition, multiplication, exponentiation, tetration, pentation, and every one of the infinitely many hyperoperators after, is:
f(a, h, b) =
if h = 0, b+1
otherwise:
if b = 0:
if h = 1, a
if h = 2, 0
if h > 2, 1
otherwise f(a, h-1, f(a, h, b-1))
And that's it! Within this function f the definitions of addition, multiplication, exponentiation, and more are included!
There are functions that grow much, much faster than any hyperoperator, but as I don't understand them fully yet, you can find them on the Googology Wiki, an extensive list of extremely large numbers.
Recursion is when a function has itself in its definition. This may seem impossible, as it would keep referencing itself forever and no result would ever be returned, as in the function
f(x) = f(x)+1.
This would be undefined for all values x:
f(x) = f(x) + 1 = (f(x)+1) + 1 = f(x) + 2 = (f(x)+1) + 2 = f(x) + 3 = ...
By repeatedly replacing f(x) with f(x) + 1, one can see that the sum just climbs to infinity. Therefore, this recursive function does not make sense. However, there are recursive functions that are well-defined, one of which is the factorial.
n factorial, written n!, is the product of all integers from 1 to n for positive integer values of n. For example, 5! = 1*2*3*4*5 = 120. The factorial can be defined recursively as follows:
n! = 1 if n = 0, and n*(n-1)! otherwise.
This definition says two things:
1. 0! = 1 - a surprising fact, but a logical way to start and "build up" the other factorials.
2. Every factorial of n where n > 1 is just n * the previous factorial.
This makes sense, as, for example, 4! = 1*2*3*4 = (1*2*3)*4 = 3!*4. Grouping together every number in the product except the last gives (n-1)!, and the number left is n.
Calculating 6! would be as follows:
6! = 6*5! = 6*(5*4!) = 6*5*(4*3!) = 6*5*4*(3*2!) = 6*5*4*3*(2*1!) = 6*5*4*3*2*1 = 720.
Recursive functions are only well-defined (for our purposes) if
a. A function f(x) doesn't have f(x), but f(x-1) or f(x-n) where n is some positive integer, in its definition.
b. It must include a stopping point, usually at x = 0.
Now, we are ready to define our function for hyperoperators.
The function f would accept three arguments - a (the first operand), h (the hyperoperator), and b (the second operand). For example, 2^4 would be written as f(2,3,4). The edge cases would be as follows:
f(a,h,b) = b+1 if h=0, because the zeroth operator is the successor function.
If b = 0, there are a few sub-cases that need to be considered:
If h = 1, f(a,1,0) = a+0 = a, so if b = 0 and h = 1, the function should return a.
If h = 2, f(a,2,0) = a*0 = 0, so if b = 0 and h = 2, it should return 0.
If h = 3, f(a,3,0) = a↑0 = 1, so if b = 0 and h = 3, it should return 1.
What if b = 0 and h > 3 - that is, what is a↑↑0, a↑↑↑0, etc.? To answer this, we need to remember why a↑0 = 1.
Start with powers of 2: 2↑1 = 2, 2↑2 = 4, 2↑3 = 8, etc. Every power of 2 is 2 times the last - that is, 2↑n = 2 * 2↑(n-1). Plugging in 1 for n, 2↑1 = 2*2↑0. Since 2↑1 = 2, 2=2*2↑0, and thus 2↑0 = 1. This holds for any number besides 2:
a↑n = a * a↑(n-1)
a↑1 = a * (a↑0)
a↑1 = a
a = a * (a↑0)
1 = a↑0
Let's extend this to tetration. 2↑↑1 = 2, 2↑↑2 = 4, 2↑↑3 = 16, 2↑↑4 = 65536, etc. Every number is 2 to the power of the last.
2↑↑n = 2↑(2↑↑(n-1))
2↑↑1 = 2↑(2↑↑0)
2 = 2↑(2↑↑0)
1 = 2↑↑0
Replace 2 with a and the proof holds. a↑↑0 = 1.
This can be further extended to any hyperoperator beyond tetration, so the last edge case would be:
If b = 0 and h > 2, f(a, h, b) = 1.
Now for the final case for the hyperoperator function, where neither b nor h are equal to 0. Since every hyperoperator is repeated application of the last,
f(a, h, b) = f(a, h-1, f(a, h-1, f(a, h-1, ... ) ... ), repeated b times. However, we can do better. Just like the factorial function grouped all numbers except the last, we can only put one "f(a, h-1," and then have the third argument be f(a, h-1, f(a, h-1, ... ) ... ), repeated b-1 times, which would be f(a, h, b-1). Now the last case has been solved:
If b ≠ 0 and h ≠ 0, f(a, h, b) = f(a, h-1, f(a, h, b-1)).
An example of this would be
2↑4 = f(2, 3, 4)
which, by this last case, is
f(2, 2, f(2, 3, 3)) = 2*2↑3
Using it on the inner function again, it becomes
f(2, 2, f(2, 2, f(2, 3, 2))) = 2*2*2↑2
and then
f(2, 2, f(2, 2, f(2, 2, f(2, 3, 1)))) = 2*2*2*2↑1.
It works! 2↑4 leads to multiplying 2 by itself 4 times! Now, the full hyperoperator function, which defines addition, multiplication, exponentiation, tetration, pentation, and every one of the infinitely many hyperoperators after, is:
f(a, h, b) =
if h = 0, b+1
otherwise:
if b = 0:
if h = 1, a
if h = 2, 0
if h > 2, 1
otherwise f(a, h-1, f(a, h, b-1))
And that's it! Within this function f the definitions of addition, multiplication, exponentiation, and more are included!
There are functions that grow much, much faster than any hyperoperator, but as I don't understand them fully yet, you can find them on the Googology Wiki, an extensive list of extremely large numbers.