Big Numbers
In one of those funny coincidences where it seems the popular mind is pregnant with an idea, an article was recently published to the programming section on reddit that mentions the busy beaver function. The article is titled “Who Can Name The Bigger Number?” and is essentially about trying to name very large integers.
The article is fairly long, but also quite interesting. The associated thread on reddit is also interesting, but is topped by a very similar discussion on the XKCD blog about naming large numbers.
The XKCD discussion is associated with a funny comic wherein he suggests calling the Ackermann function with Graham’s number to horrify mathematicians.
The Ackermann function is a computable function that is not primitive recursive, and grows astoundingly fast (though, as noted elsewhere, apparently not as fast as the busy beaver function).
Graham’s number is a number so ridiculously huge that it cannot be meaningfully expressed in scientific notation. Instead, a special notation had to be invented to write it down. This number acctualy has a practical (?) use: it is currently the smallest upper bound on an unsolved problem from a field of mathematics called Ramsey theory. The current lower bound? Six. That’s right… We know for a fact that the smallest answer to this question is 6, and the largest is greater than the number of seconds since the big bang, plus the number of atoms in the universe, plus the total number of possible chess games, plus… you get the idea.
Or maybe you don’t. Put it this way. If we turned every atom in the universe into pen and paper, there wouldn’t be enough matter to write out this number in base 10 notation. If we had a printer that was able to magically make paper and ink out of thin air, and was capable of printing a billion sheets of paper in 1 second, and set it to printing this number, it wouldn’t be done for several hundred trillion years. For that matter, it wouldn’t even be able to print out a googolplex in under several hundred billion years. (A google is a 1 followed by 100 zeros, or 10^100. A googolplex is a 1 followed by a google of zeros, or 10^(10^100). Most people only know out to billion, which is a 1 followed by 9 zeroes or 10^9, or a trillion, 1 followed by 12 zeros or 10^12.) In the mean time, all that paper would completely fill the universe several times over.
Needless to say that when you take a function that grows insanely fast, and feed it a number that is basically inconceivably large, you get another number that simply defies conception.
Of particular note, from these threads I stumbled across an interesting “game” called MineField, apparently developed by Bram Cohen.
Essentially, the game is about naming large numbers, and as is pointed out in some of the threads listed above, this eventually turns into a game of developing stronger logics. Apparently this is the case because there is a limit to the complexity of a statement in a given logic. I’m going to hazard a guess and say this is directly related to the Berry Paradox, a subject on which I intend to write my next entry.
MineField makes the connection to stronger logics explicit, by setting up the game in such a way that on a given players turn, they can add a new axiom to the shared logic the players are using to describe numbers. They start with an axiomatic basis of set theory, any of the common bases which are accepted as consistent. So a player adds an axiom to the logic, and uses the now stronger logic to name an infinite number.
There are a few more details relating to how to “win” the game, but I leave it to the reader to click through if interested.