6 ms·
Busy beaver hunters reach numbers that overwhelm ordinary math
- tocs3 1y agoI 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?
- adgsfhj 1y agoFictionally, 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. https://archive.org/stream/SpaceOdyssey_819/3001_The_Final_Odyssey_-_Arthur_C_Clarke_djvu.txt https://archive.org/stream/SpaceOdyssey_819/3001_The_Final_O...
- db48x 1y agoI loved that part of the book. I thought it was so cool how they thoroughly scrubbed the Internet of these dangerous programs, and then stored the very last copy on a disk in an ancient lava tube on the moon, just in case.
- twiceaday 1y agohttps://www.scottaaronson.com/papers/bb.pdf https://www.scottaaronson.com/papers/bb.pdf This paper contains many conjectures around BB that could be interesting to some.
- gpm 1y agoCollatz conjecture - and I would have said that even before we solved BB up until it reduces to collatz-like problems.
- poulpy123 1y agoAh yes the totally new math of exponentiation
- xelxebar 1y agoPentation? 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: https://www.youtube.com/playlist?list=PL3A50BB9C34AB36B3 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.
- Workaccount2 1y agoThere is something awesome about incredibly large finite numbers. People gush about infinity, but I find it to be a pretty boring concept compared to finite numbers too large to even be written in this universe.
- xelxebar 1y agoIndeed! Funnily enough, there seems to be something similar going on between defining large finite numbers and defining large countable cardinals.
- Waterluvian 1y agoYeah! Like, there is a perfectly finite number, but is so large that there simply isn’t enough information in the universe to encode it in any format. How cool is that to just think about for a while?
- charcircuit 1y agoThere is enough information if you assume reality is continuous. Pick a point A to be the origin. Then then you can encode the number by placing something at 1/N meters away from the origin.
- xenotux 1y agoThere 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.
- defrostr 1y agoI usually get drawn into their posts also and didn’t realize they were low value; my IQ must not be high enough to differentiate. What would you recommend as alternative sources?
- lutusp 1y agoDon't let specialists detract from your enjoyment of Quanta-level articles. This one is well-written, makes no egregious errors, and only omits one important fact. And that fact is ... All this talk about exponentiation, tetration and pentation have their roots in Peano arithmetic, which for reasons of logical clarity, defines precisely one function -- the "successor function": s(n) = n+1 Using just this function, Peano defines addition, multiplication and exponentiation with great clarity. Since Peano's time, people have been making adjustments, like including zero among the counting numbers, and by extending exponentiation into tetration, pentation and a few more exotic operations fully discussed in the linked article and elsewhere. I personally would have liked to see a more complete exposition of the logical roots of the Busy Beaver challenge, and I think the missing parts would have made the article a better read, even for non-specialists. Maybe especially for those readers. But Quanta articles are perfectly suited to their audience, people who may be inspired to look for more depth elsewhere.
- QuesnayJr 1y agoThere isn't really anything better. The Notices of the AMS has one feature article each issue, but those are sometimes too technical. Anyway, this article seems fine to me. The "exponentiation" comment seems like a bizarre misreading. The article is just trying to explain how big BB(6) is. Before that, it explains what BB(n) is. To think it's solely about exponentiation you have to skip that entire section.
- lutusp 1y agoHmm, 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.
- brap 1y agoAt some point you gotta wonder if there’s even a difference between “stops after N” and “never stops”. I mean obviously there is, it’s the same difference between N and infinity. But… is there really?
- dwohnitmok 1y agoWelcome to ultrafinitism!
- lanternfish 1y agoIn 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.
- fuckaj 1y agoWell since we got off the Gold standard, we might need those big numbers.
- wodenokoto 1y agoNumberphile just did a video on subcubic graph numbers which grows much, much faster than Tree numbers. Do we know if they grow faster than busy beavers? https://youtu.be/4-eXjTH6Mq4 https://youtu.be/4-eXjTH6Mq4
- francoi8 1y agoBusy Beaver is non computable and grows much faster than the various subcubic graph numbers (you could easily encode a subcubic graph number computation in a relatively small turing machine).
- Certhas 1y agoNo. The busy beaver function grows faster than any computable function. What's more, for any N > 549, you cannot prove (in the usual universe of mathematics) that any computable number is equal to or larger than BB(N). (At least that's my understanding of the independence results (https://wiki.bbchallenge.org/wiki/Independence_from_ZFC https://wiki.bbchallenge.org/wiki/Independence_from_ZFC))
- andrepd 1y agoTREE(3) is so crazy to me. You would expect it to either be a reasonable number, or to be infinite (i.e. there's an infinite sequence of such trees). But no. It's just an _impossibly unfathomably large number_. Eventually, there's no more trees with less than $i$ vertices, but only at such a stupid incredibly large $i$ that it makes other "googology" numbers vanish by comparison.
- tromp 1y ago> it makes other "googology" numbers vanish by comparison. I consider TREE to be medium sized in the googology universe. It obliterates Graham's Number of course, as well as Goodstein sequence and simple hydras. But it's easily bested by an ingenious matrix generalization of hydras known as the Bashicu Matrix System, even when fixed at 2 rows. 3-row BMS goes far beyond that, let alone n-row. BMS is so simple that it can be encoded in under 50 bytes [1], where TREE would take significantly more. Beyond that there vastly greater numbers still such as Loader's Number. I shouldn't mention Rayo's because that's no longer computable in the usual sense. [1] https://codegolf.stackexchange.com/questions/18028/largest-number-printable/273656#273656 https://codegolf.stackexchange.com/questions/18028/largest-n...
- mistercow 1y ago> 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.
- JohnKemeny 1y ago"this question" is Given the code of a computer program, can you tell whether it will eventually stop or run forever? It is indeed the Halting problem. (Except that they forgot to state what the input is (the code itself).
- smallerize 1y ago)
- Kranar 1y agoThe objection, which I agree with, is to the statement "Any method that works for some programs will fail for others, and in some cases, no method will work." There is no case where no method whatsoever will work. It's true that for any method, there are cases where it fails but it's not true that there exist cases for which every method fails.
- mistercow 1y agoYeah, apparently I didn’t communicate that well enough. But I think this is a subtle and common point of confusion. There are machines which are very, very hard to determine whether they halt or not, and so people end up thinking that there must be specific machines for which no Turing machine can decide halting correctly. But that’s just not true. Every “attempted halting decider” has its own infinite set of failure cases, which are specific to that machine, and not fundamental to the input machines. This feels really strange, and trying to turn that other intuitive sense into something meaningful and reasonably formal is an interesting exercise, but it’s tricky.
- adinhitlore 1y ago[flagged]
- noiv 1y agoI wonder, whether there's anything interesting on the tape after a BB(5/6) halts?
- fwip 1y agoYou can read about the BB5 winner here - it looks like the final tape state is 4,098 ones in a row: https://bbchallenge.org/1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA?w=250&ox=0.8 https://bbchallenge.org/1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA?w... https://wiki.bbchallenge.org/wiki/5-state_busy_beaver_winner https://wiki.bbchallenge.org/wiki/5-state_busy_beaver_winner
- shawnz 1y agoSee also https://news.ycombinator.com/item?id=44406171 https://news.ycombinator.com/item?id=44406171