Ackermann function
In this function, there are a lot of definitions related to Ackermann function, but one of the most commonly used is the definition made by Robinson. Don't worry, we also have another definition as well. It is a recursive function.
It is commonly referred as A(x,y). Its growth rate in fast growing hierarchy is f(ω) (n).
Robinson's definition of this function
As mentioned before, it is the most common version of the function. Its definition is as follows:
when x=0, A(x,y) = y+1,
when y=0, A(x,y) = A(x-1,1) (if x>0)
If none of the above applies, A(x,y) = A(x-1,A(x,y-1)).
For example, let's have a look at A(3,3):
A(3,3) = A(2,A(3,2))
= A(2,A(2,A(3,1)))
= A(2,A(2,A(2,A(3,0))))
since y=0, A(3,0) is simplified to A(2,1)...
= A(2,A(2,A(2,A(2,1))))
= A(2,A(2,A(2,A(1,A(2,0)))))
= A(2,A(2,A(2,A(1,A(1,1)))))
= A(2,A(2,A(2,A(1,A(0,A(1,0))))))
= A(2,A(2,A(2,A(1,A(0,A(0,1))))))
since x=0, A(0,1) is simplified to 1+1 = 2...
= A(2,A(2,A(2,A(1,A(0,2)))))
= A(2,A(2,A(2,A(1,3))))
= A(2,A(2,A(2,A(0,A(1,2)))))
= A(2,A(2,A(2,A(0,A(0,A(1,1))))))
= A(2,A(2,A(2,A(0,A(0,A(0,A(1,0)))))))
= A(2,A(2,A(2,A(0,A(0,A(0,A(0,1)))))))
= A(2,A(2,A(2,A(0,A(0,A(0,2))))))
= A(2,A(2,A(2,A(0,A(0,3)))))
= A(2,A(2,A(2,A(0,4))))
= A(2,A(2,A(2,5)))
= A(2,A(2,A(1,A(2,4))))
= A(2,A(2,A(1,A(1,A(2,3)))))
= A(2,A(2,A(1,A(1,A(1,A(2,2))))))
...
= A(2,A(2,A(1,A(1,A(1,A(1,A(1,A(2,0))))))))
= A(2,A(2,A(1,A(1,A(1,A(1,A(1,A(1,1))))))))
= A(2,A(2,A(1,A(1,A(1,A(1,A(1,A(0,A(1,0)))))))))
= A(2,A(2,A(1,A(1,A(1,A(1,A(1,A(0,A(0,1)))))))))
= A(2,A(2,A(1,A(1,A(1,A(1,A(1,A(0,2)))))))
= A(2,A(2,A(1,A(1,A(1,A(1,A(1,3))))))
= A(2,A(2,A(1,A(1,A(1,A(1,A(0,A(1,2)))))))
... (after multiple (hundred) steps)...
= A(0,60)
= 61
Yikes! This process takes so long to solve! Luckily, there is a relation with arrow notation/ hyper operators which DEFINITELY simplifies the over-complicated process!
A(x,y) = 2↑(x-2) (y+3) - 3 = 2[x](y+3) -3 (where [] means hyper-operator)
Examples:
A(3,3) = 2↑6 - 3 = 64 - 3 = 61 (MUCH faster than the equation above!)
A(3,4) = 2↑7 - 3 = 128 - 3 = 125
A(4,4) = 2↑↑7 - 3 (approximately 10^10^10^19728)
Friedman's version
It is defined as follows: (reference)
A(x,y) = 2 when y=1
A(x,y) = 2y (if x = 1, y > 1)
A(x,y) = A(x-1,A(x,y-1)) (if x>1 & y>1)
So, A(x,y) is defined for all positive integers, and it is equal to 2 ↑(x-1) y in arrow notation.
Examples:
A(3,3) = 2↑↑3 = 16 << A(3,3) using Robinson's definition, which is 61
A(3,4) = 2↑↑4 = 65536 (much, Much, MUCH LARGER than A(3,4) using Robinson's definition, which is only 125)
A(4,4) = 2↑↑↑4 = 2↑↑65536 (definitely left the other definitions in the dust)
This definition grows even faster and simpler than the Robinson's one, especially when it comes to arrow notation equivalent as it is easier to evaluate.
Uses in googology
In some cases, it can be alternatively referred to a single argument iff (If and only if) A(n) = A(n,n). A(n) is also a basis of gag names. (using Robinson's definition)
The similar function, called Ackermann numbers (even though not related), still exhibits similar growth rate. It is defined as follows;
A(n) = n↑(n) n
example: A(4) = 4↑↑↑↑4.
There is a function that is based on this function. It is called a multivariable Ackermann function, and it exhibits growth rate of f(ω^ω) (n), which is similar to other linear array notations, which will be covered later in this chapter.
The numbers that I will coin using that notation will have its own page in the List of Numbers, along with the multivariable Ackermann function. Stay tuned!