Hello, Hypers!
Numbers are infinite. Math allows us to play with the infinity although none of us has experienced it. There is strong evidence supporting that our Universe has not existed forever. It had a beginning and will probably have an end. Thus, not even the oldest particles on it have an infinite life, whatever that means.
There is also strong evidence telling us that the Universe's extension might also be finite. This means the number of galaxies, stars, planets, and particles is not infinite. These limits on time and space give us a reference to tell what can be considered a big number.
Computability Theory, the first and most fundamental field in Computer Science, has a lot to do with big numbers. In this article, I don’t want to deal with computational concepts. I plan to talk about computable numbers in a future article. Today, I want to show you the limits of human imagination. How far our minds can go in the seek of large numbers and whether these numbers are really large.
But, most importantly, I’ll do my best to make you have a lot of fun in the meantime.
Note: Do you want to read some of my articles on infinity? Try this one
Our Reference for a Large Number
The word atom comes from ancient Greece and it means indivisible. Many decades ago, we discovered that atoms are divisible LOL. They are composed of subatomic particles known as neutrons, protons, and electrons. Protons and neutrons contain other subparticles while electrons are elemental particles.
However, out of the atomic organization, subatomic particles don’t create anything useful. So, for practical purposes (and because calculating the number of subatomic particles in the universe is too hard), I’ll consider atoms as our basic unit.
Note: From now on, and due to Substack lack of support for inline Latex, I’ll use m^n to represent the n-th power of m. For example, 10^6 is 10 to the power of 6 or one million.
All this jibber-jabber about particles and atoms is intended to find a reference of what a big number is. For example, one cell has about 10^14 atoms. That’s 100 trillion atoms. The human body contains 37.2 trillion cells approximately which means it contains about 3.7*10^27 atoms. Our Sun contains 1.4*10^57 atoms and the entire observable Universe has approximately 10^80.
So, 10^80 can be considered a really large number. It is a one followed by 80 zeros. The total number of atoms in the Universe we know. Now, we have a practical reference of what a large number is.
Getting Large Numbers from Math Functions
Now let’s explore some functions that give us large numbers in no time. I’ll explain myself with an example: the factorial function.
The factorial function is defined as f(n) = 1*2*3*…*n
. In other words the product of all natural numbers up to n.
This function is usually denoted as n!
. As you can imagine this function grows incredibly fast when n
increases. These are some of the values of this function:
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
…
10! = 3628800
…
60! = 8.3*10^81
Wow, 60!
is already bigger than the number of atoms in the observable Universe. Now let’s take the exponentiation: exp(m, n) = m^n.
For example, exp(2, 3) = 2^3 = 2*2*2 = 8.
You can quickly realize that exp(n, n) > n!
for any n
greater than 1. Then, in some way, we can say that exponentiation grows even faster than the factorial function. In particular exp(50, 50) = 8.8*10^84.
Long multiplications like the ones performed in factorial and exponentiation functions seem to reach what we call a large number in no time. But, is there a way to get there even faster?
Recursion
I know, I said I wasn’t going to talk about computability but please, let me just neglect this promise a little bit. You won’t regret it.
Factorial and exponentiation functions can be expressed differently. They can be expressed in terms of themselves. This is what we call a recursion. For example, factorial can be written as:
1! = 1
n! = n*(n-1)!
In the first line, we defined a base case. In this case, it is the value of 1!. Then we add the recursive definition. This recursive definition uses the factorial function itself. To better understand how it works, let’s try to calculate 3! according to this definition.
3! = 3 * (3-1)! = 3*2! = 3*2*(2-1)! = 3*2*1! = 3*2*1 = 6
We first apply the recursive definition to get 3*2!, then we apply it again to get 3*2*1!, and finally, we apply the base case (1! = 1) to get 3*2*1=6.
Exponentiation can also be defined recursively:
exp(n, 1) = n
exp(n, m) = n * exp(n, m-1)
Now you can calculate 2^3 using this recursive definition.
But, why am I talking about recursion? This looks like an alternative to define functions that we already know how to define using multiplications and exponentiation. Is recursion hiding something?
The Ackermann Function
If I ask you to come up with the biggest function you can imagine, you’ll probably use a lot of exponentiation. But what if I tell you that your function won’t be as large as one that only uses sums?
Well, to be fair, this function also uses another operation: recursion. Without further ado, this is the Ackermann Function:
A(0, n) = n+1
A(m+1, 0) = A(m, 1)
A(m+1, n+1) = A(m, A(m+1, n))
Besides being a more sophisticated recursive function, the Ackermann Function doesn’t seem to be larger than factorial or exponentiation. It is only summing one here and there. It seems impossible this function grows as fast as the ones we’ve seen previously. This is the power of recursion, it strikes from the shadows.
Note: The original function published by Wilhem Ackermann didn’t look like this one. This definition was published by the Hungarian mathematician Rózsa Péter.
For example, let’s calculate A(2, 0):
A(2, 0) = A(1, 1) = A(0, A(0, 1)) = A(0, 2) = 3
This function seems inoffensive! Now try to calculate A(4, 2). I won’t do it in this article. And it’s not because I don’t want to do it, it’s because I can’t do it. The reason: A(4, 2) = 2^65536 - 3.
This is a ridiculous number! Consider that 10 < 2^4
, then 10^80 < 2^320
. In other words, the number of atoms in the observable Universe is less than 2^320
and this number is nothing compared to 2^65536
. This is like a one followed by 16384 zeros. Can you imagine a number with 16385 digits? We said that it is hard to count the number of subatomic particles in the observable Universe but it’s almost sure that counting them all including the unknown dark matter and dark energy will result in a number still ridiculously lesser than A(4,2).
As large as this number can be, it is nothing compared with A(4, 3).
Yes, just by incrementing n by one, we get an incredibly larger number. Specifically, we get 2^(2^65536) - 3
. Just by incrementing n by one, we get 2 to the power of the incredibly large previous number. Although the previous number - A(4,2)
- was large, it still could be written. We saw it has 16385 digits. Now this new number has about A(4, 2)
digits. This makes it physically impossible to write it in our entire Universe. Writing a digit of this number in every subatomic particle is not enough to represent it.
And this is only A(4, 3)
. It just doesn’t make sense to keep talking about greater inputs. So, remember, don’t mess with Ackermann Function because it can break your computer :)
Conclusion
Recursion is more than just an alternative way of defining a function or a different mindset. It gives us the ability to create new and unique things. The Ackermann Function has a great significance in Computer Science. It opened our eyes to a new Universe of functions that were relevant in defining what can be computed and what not.
Now, some questions may arise. For example, is it possible to define the Ackermann Function without recursion? Why is this function so huge? What is it doing under the hood? Is it the bigger function we can define?
I’ll stop here for now but let me know if you want more articles answering these questions. Don’t forget to share this post with anyone interested in these topics.
See you next Tuesday!
Solid article, I didn't expect less from you, but I have a question: You say that A (4, 3) has A (4, 2) digits? This is exact? If so, how?
And a simple suggestion: The article is perfectly conducted until the definition of the Ackerman function when it just becomes harder to follow if you are not familiar with Computer Science, I don't know if I have explained myself.
But again, great article!!!!
Love it! I did a halting problem article a while ago, so maybe we should do a collab on why recursion and iteration are two sides of the same coin, and what does Ackerman and Halting have in common. What do you say?