Numbers so large [footnote] you can barely express them and not possibly fathom them.
The Busy Beaver function
FTA: … the busy beaver game consists of designing a halting Turing machine with alphabet {0,1} which writes the most 1s on the tape, using only a given set of states. The rules for the 2-state game are as follows:
1 the machine must have at least two states in addition to the halting state, and
2 the tape initially contains 0s only.
A player should conceive a transition table aiming for the longest output of 1s on the tape while making sure the machine will halt eventually.
An nth busy beaver, BB-n or simply "busy beaver" is a Turing machine that wins the n-state busy beaver game. That is, it attains the largest number of 1s among all other possible n-state competing Turing machines. The BB-2 Turing machine, for instance, achieves four 1s in six steps.
Determining whether an arbitrary Turing machine is a busy beaver is undecidable. This has implications in computability theory, the halting problem, and complexity theory. The concept was first introduced by Tibor Radó in his 1962 paper, "On Non-Computable Functions". [emphasis mine. I have a particular fondness for undecidable/uncomputable functions.]
... The n-state busy beaver (BB-n) game is a contest to find such an n-state Turing machine having the largest possible score — the largest number of 1s on its tape after halting. A machine that attains the largest possible score among all n-state Turing machines is called an n-state busy beaver, and a machine whose score is merely the highest so far attained (perhaps not the largest possible) is called a champion n-state machine.
[This all sounds kinda sweet, innocent, and nerdy so far, doesn't it? But get this:]
The busy beaver function quantifies the maximum score attainable by a busy beaver on a given measure. This is a noncomputable function. Also, a busy beaver function can be shown to grow faster asymptotically than any computable function.
[Holy. Fucking. Shit. Let's say that again: ... grow faster asymptotically than any computable function. That is, in the limit, this function grows so fast that mathematics cannot even express how fast it grows. Yikes! You gotta love this. Mathematics is the best tool we have for understanding the universe. The best tool we have for understanding reality. But as Gödel famously proved, it cannot tell us all truths. [Footnote 2]]
#Math #Wonder #Complexity #BusyBeaver
Footnote: It is a mistake to refer to any integer as “large”. Let us define a number, x, as “large” if there are more numbers smaller than x than there are larger than x. For example, we can reasonably define a person, p, as “large” if there are more more people smaller than p than there are larger than p. By this criterion, I am a small person.
Consider any integer, x. If x is an integer, then x is necessarily finite. [Picture me at a kiosk with a sign reading, “Infinities are not numbers. Prove me wrong.” ;-)]
For any integer x, there is an infinity of integers larger than x, but only a finite number of integers smaller than x. (The argument becomes more complex with real numbers.) Therefore, by definition, every integer is small. QED
Footnote 2: Republicans would seize on this fact and exploit it to lie to people except that they and their base are far too fucking stupid to understand what it means.
https://en.wikipedia.org/wiki/Busy_beaver
