I really like the Busy Beaver stuff. I wish I had been exposed to it (at lest enough to play with it some) in high school. It reminds me some of Jorge Luis Borges' story "The Library of Babel".
Does anybody know of other interesting problems in the Busy Beaver space?
Fictionally, maybe the Mandelbrot Maze mentioned in Arthur C. Clarke’s 3001:
> Their approach
was more subtle; they persuaded their host machine to initiate a program which
could not be completed before the end of the universe, or which - the
Mandelbrot Maze was the deadliest example - involved a literally infinite series
of steps.
Pentation? How quaint. For other Large Number fans, David Metzler has a wonderful playlist that goes way down the rabbit hole of the fast growing hierarchy:
Almost all of these mind-bogglingly large numbers are built around recursion, like the Ackermann function, which effectively has an argument for the number of Knuth up arrows to use. Then you can start thinking about feeding the Ackermann function into that slot and enjoy the sense of vertigo at how insane that becomes.
I find it fascinating how quickly the machinery of specifying large numbers probes the limits of what's definable within the mathematical systems we use.
If you have a child who likes math I highly recommend "Really Big Numbers" by Richard Schwarz. Tons of nice illustrations on how to "take bigger and bigger steps".
It's funny how, for a certain subset of math, a researcher's life can be condensed to "arguing about which number is the biggest (preschool)" -> "learning about math" -> "arguing about which number is the biggest (academia)"
You might already know this, but the busy beaver function grows faster than any computable function. So although the best known lower bound of BB(6) can be expressed with just pentation, generally speaking the BB function is certainly beyond any standard operation in terms of fast growth
The growth of BB is certainly mind-boggling; however, I personally find its growth rate so untouchable as obviate any attempt at understanding. There's nothing to gain purchase on.
The fast growing hierarchy, on the other hand, provides oodles of structure for us to explore, and we can construct numbers that are vastly larger than anything BB(6) is likely to hit. In fact, this is why we use the fast growing hierarchy to approximate really big numbers all the time!
When we take something like f_Γ_0 and try to unpack even just the barest surface of its size, I get a feeling of vastness similar to those videos of diving endlessly into fractals.
There is a downvoted comment that reads "ah yes the totally new math of exponentiation". The snark is uncalled for, but that's actually the essence of this article: it talks about repeated exponentiation as if it were some profound mathematical discovery.
It isn't. The article neglects to explain what makes busy beaver numbers interesting in the first place. And I think it's symptomatic of Quanta Magazine articles that feature on HN several times a week. A profoundly-sounding title and pleasant writing, but not much essence beyond that.
It's crazy to me that we're now writing articles about the fact that a large number is large.
Hey guess what, I can imagine a number even larger. It's BB(6) + 1, isn't that amazing and interesting? Wow imagine BB(6) multiplied by a googolplex, amazing. Wow, such number.
What's the point? Numbers are infinite, what else is new?
Hmm, what a shame that the LaTeX content wasn't properly rendered in the linked article. When I noticed this I assumed someone had forgotten to include the MathJax JavaScript library, which, when present, converts LaTeX notation into properly rendered LaTeX client-side.
As it turns out, the MathJax library is called from the article's HTML (in line 1765), but for some reason it's not working.
A long-running debate argues that LaTeX rendering should be a default browser feature, so far without success. In the meantime MathJax works pretty well unless someone disables JavaScript client-side.
Reasonable people may differ, but not being able to render LaTeX is egregious and wrong.
In a mathematical sense - absolutely. You can dual halting problem against many very tangible qualities - like whether a (proved) statement is true or false. A (large-n) halting program is closer to an instantly halting program not just because n is always closer to 0 than inf, but because 'large n halting' and 'instantly halting' are ontologically similar in a way they just aren't with unhalting programs.
> In 1936, the pioneering logician Alan Turing proved that there’s no universal procedure for answering this question, which became known as the halting problem. Any method that works for some programs will fail for others, and in some cases, no method will work.
This is weirdly stated. The first sentence is correct. But trivially, either a machine that always says “yes” or a machine that always says “no” will give the correct answer for any given case.
Given a particular set of axioms, there are machines which do not halt, but which cannot be proven not to halt, and maybe that’s what the article means. But that’s going beyond the halting problem.
22 comments
[ 2.8 ms ] story [ 36.0 ms ] threadDoes anybody know of other interesting problems in the Busy Beaver space?
> Their approach was more subtle; they persuaded their host machine to initiate a program which could not be completed before the end of the universe, or which - the Mandelbrot Maze was the deadliest example - involved a literally infinite series of steps.
https://archive.org/stream/SpaceOdyssey_819/3001_The_Final_O...
This paper contains many conjectures around BB that could be interesting to some.
https://www.youtube.com/playlist?list=PL3A50BB9C34AB36B3
Highly recommended.
Almost all of these mind-bogglingly large numbers are built around recursion, like the Ackermann function, which effectively has an argument for the number of Knuth up arrows to use. Then you can start thinking about feeding the Ackermann function into that slot and enjoy the sense of vertigo at how insane that becomes.
I find it fascinating how quickly the machinery of specifying large numbers probes the limits of what's definable within the mathematical systems we use.
"Infinity is farther away than you thought."
The fast growing hierarchy, on the other hand, provides oodles of structure for us to explore, and we can construct numbers that are vastly larger than anything BB(6) is likely to hit. In fact, this is why we use the fast growing hierarchy to approximate really big numbers all the time!
When we take something like f_Γ_0 and try to unpack even just the barest surface of its size, I get a feeling of vastness similar to those videos of diving endlessly into fractals.
It isn't. The article neglects to explain what makes busy beaver numbers interesting in the first place. And I think it's symptomatic of Quanta Magazine articles that feature on HN several times a week. A profoundly-sounding title and pleasant writing, but not much essence beyond that.
Hey guess what, I can imagine a number even larger. It's BB(6) + 1, isn't that amazing and interesting? Wow imagine BB(6) multiplied by a googolplex, amazing. Wow, such number.
What's the point? Numbers are infinite, what else is new?
As it turns out, the MathJax library is called from the article's HTML (in line 1765), but for some reason it's not working.
A long-running debate argues that LaTeX rendering should be a default browser feature, so far without success. In the meantime MathJax works pretty well unless someone disables JavaScript client-side.
Reasonable people may differ, but not being able to render LaTeX is egregious and wrong.
I mean obviously there is, it’s the same difference between N and infinity. But… is there really?
Do we know if they grow faster than busy beavers?
https://youtu.be/4-eXjTH6Mq4
This is weirdly stated. The first sentence is correct. But trivially, either a machine that always says “yes” or a machine that always says “no” will give the correct answer for any given case.
Given a particular set of axioms, there are machines which do not halt, but which cannot be proven not to halt, and maybe that’s what the article means. But that’s going beyond the halting problem.