4 ms·
Latest Busy Beaver champion has too many digits to count
- fn-mote 4y agoThis looks like a really cool topic... but you need to know the basic definitions in order to understand the article or its parent. https://webusers.imj-prg.fr/~pascal.michel/tmi.html https://webusers.imj-prg.fr/~pascal.michel/tmi.html Quoted so you don't have to dig for it: What is a busy beaver? Consider Turing machines with fixed numbers of states and symbols. If there are k states and n symbols, then the number of possible next move functions, or possible tables, is (2kn+1)^kn. Thus, there are (2kn+1)^kn Turing machines with k states and n symbols. Each of them can be launched on a blank tape, that is a tape with symbols 0 in all cells. Then some of them never stop, and the other ones eventually stop. Those which stop are called busy beavers. Busy beavers compete in two competitions: to take the most time to stop, to leave the most non-blank symbols on the tape when stopping.
- vanderZwan 4y agoIt feels a bit similar to how Conway's Game of Life is a surprisingly deep rabbit hole with its own devoted niche community. I wonder how many of those types of math/programming niches exist.
- JadeNB 4y ago> It feels a bit similar to how Conway's Game of Life is a surprisingly deep rabbit hole with its own devoted niche community. I wonder how many of those types of math/programming niches exist. I'm not a programmer, though I suspect that that community is similar, except perhaps with fewer rabbit holes now just because it's younger—but research-level mathematics is essentially nothing but one after another rabbit hole with a devoted niche community. There's no topic so specialized that you can't find a mathematician for whom it's their everyday concrete research lab, and no mathematician so specialized that you can't find a topic even in their discipline on which they'll look down as meaninglessly abstract and application-free.
- ravi-delia 4y agoWith BB it's not so surprising that it's weird because if it weren't, you could cheat! Say you know that a Turing machine which computers digits of the goldbach conjecture has n states. Then if you could just get BB(n), or even if BB(n) is too predictable, you could just run that Turing machine for over BB(n) steps and know it doesn't halt. So we can informally see that BB will necessarily be at least as hard as all of math. Nature abhors a vacuum, but math abhors a shortcut. Every time we find one, it turns out to be deeper and more beautiful than expected.
- Hercuros 4y agoTo be fair, even if you were able to get BB(n), it might still be (and probably is) some ridiculously large number, like a billion times the number of atoms in the universe or something. So that wouldn't really help you solve any math problems even if you were able to get the maximum amount of steps For a lot of things, like solving boolean SAT, we have the equivalent of a "busy-beaver" limit: if you want to solve a SAT instance of size n, you need at most 2^n steps. And being able to solve arbitrary SAT instances in reasonable time would be huge for mathematical proofs as well, because you could do stuff like find proofs up to a fixed size quickly. Point is that math is probably even harder than BB in some sense, since having BB would not really help you solve math problems in practice most likely.
- ravi-delia 4y agoOh absolutely, you could never actually use BB(n) even with an oracle on hand. I simplify to cheating on math mostly because it's sort of crazy to think about coming at a problem from that angle (if the Goldbach conjecture is false there's obviously some N where it stops holding, but it's bizarre that you can formulate an N which is independent of the question), but really BB is hard because it's such a slight relaxation of the halting problem. It is a little more interesting (to me at least) than SAT because you expect SAT to be as hard as math. I mean, it's basically just a proof done the long hard way. But even though BB(n) doesn't provide an especially useful upper bound, it does let you expand the halting problem out large enough to use as a bludgeon, since even having information about BB(n) would still let you cheat. It's fun that way!
- flobosg 4y agoRelated: “Who Can Name the Bigger Number?” – https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html
- macspoofing 4y agoRelated Numberphile videos: - Rayo's Number: https://www.youtube.com/watch?v=X3l0fPHZja8 https://www.youtube.com/watch?v=X3l0fPHZja8 - TREE(3): https://www.youtube.com/watch?v=3P6DWAwwViU https://www.youtube.com/watch?v=3P6DWAwwViU
- tim_hutton 4y agoAs a Golly file, so you can run it for yourself: https://github.com/GollyGang/ruletablerepository/raw/gh-pages/downloads/PavelKropitz_t15.zip https://github.com/GollyGang/ruletablerepository/raw/gh-page... (4kB) In Golly: File > Open Pattern... > open the zip itself (don't unzip first).
- AlbertoGP 4y agoAh, fond memories of first learning about Busy Beavers in A.K.Dewdney’s column in the Spanish edition of Scientific American (“Investigación y Ciencia”) as a kid: https://www.investigacionyciencia.es/revistas/investigacion-y-ciencia/monumento-azteca-161/una-trampa-computarizada-del-castor-afanoso-la-ms-productiva-de-las-mquinas-de-turing-2062 https://www.investigacionyciencia.es/revistas/investigacion-... I made my own Turing Machine emulator for my Commodore 64 to play with this, using the screen memory as tape to speed it up: modifying the tape was immediately reflected on the screen with no other processing needed, saving precious cycles. That made for quite a small tape, but allowed even my crude BASIC implementation to run fast, or so I remember it. The original article in English appeared in the August 1984 magazine, and the translated ones in October of that same year: https://www.jstor.org/stable/24969427 https://www.jstor.org/stable/24969427 If you can read Russian or Italian, you can find the full article here: Russian: https://gudleifr.forum2x2.ru/t98-topic#1254 https://gudleifr.forum2x2.ru/t98-topic#1254 Italian: https://archive.org/details/divertirsiconilcalcolatore/page/n85/mode/2up https://archive.org/details/divertirsiconilcalcolatore/page/... I quote the historical introduction from the English version: > “With the possible exception of bees, beavers are the busiest animals alive. All day they ply quiet northern waters bringing twigs and branches to their dam. It was undoubtedly this behavior that led Tibor Rado of Ohio State University to name a certain Turing-machine problem the Busy Beaver Game. In the early 1960’s Rado wondered how many 1’s a Turing machine could be made to print before it halted. Specifically, if a Turing machine with n possible states begins to work on a tape filled with 0’s, what is the largest number of 1’s it can print on the tape before coming to a stop? The answer is known for n = 1, n = 2, n = 3, and n = 4 but not for n = 5 or for any value of n grater than 5.”
- sligocki 4y agoHello, I'm the author. Ask me anything :) Thanks fn-mote for providing some context. In fact, I think you could appreciate most of this article without even knowing anything about Turing Machines. I spend almost the entire article just answering the question: Given a set of exponential transition rules, starting from C(5), does iterating these rules ever lead to Halt(N)? If so, in how many iterations? And what is the value of N in that case?