5 ms·
Cool post. Moving the goalposts a little bit, since it's not the same Busy Beaver problem that's normally considered. I think that its an interesting problem in
by Y_Y 5y ago
Cool post. Moving the goalposts a little bit, since it's not the same Busy Beaver problem that's normally considered. I think that its an interesting problem in its own right, but deserves a different label, since the beaver never halts but rather gets bored and wanders off.
- robbedpeter 5y agoADHD Aardvark, maybe?
- codeulike 5y agoMakework Manatee?
- Y_Y 5y agoDiligent Dingo
- sdenton4 5y agoProlific Pangolin Interminable Ibex Verbose Vervet
- pdpi 5y agoThis thread reminds me of how Ubuntu has wonderfully memorable release codenames
- nathell 5y agoCanonical missed a great opportunity by not naming 18.04 „Busy Beaver”.
- Pet_Ant 5y agoThat might have been a poor choice for Googleability.
- wruza 5y agoOn the contrary I’m always confused with these names, especially when sites refer by name only or year only. Bionic <-> 16, 18, 20? No clue. Focal minus Bionic is 4. Are these separated by one, two or four years? No idea, always have to google it.
- nextaccountic 5y ago> Moving the goalposts a little bit, since it's not the same Busy Beaver problem that's normally considered. What's the difference?
- Kranar 5y agoThe machines used in the article don't have to halt whereas the busy beaver only admits Turing machines that halt. For the purpose of this article the Turing machine either has to halt or has to enter some kind of degenerate state where it can still technically run forever but is in some sense stuck in a trivial infinite loop. The precise details of this degenerate state are explained in this article: https://nickdrozd.github.io/2021/01/14/halt-quasihalt-recur.html https://nickdrozd.github.io/2021/01/14/halt-quasihalt-recur.... This degenerate state is known as quasihalting. The author points out that for the traditional busy beaver function, let's call it BB, then BB(4) = 107. For this modified busy beaver function, let's call it, QQ, QQ(4) ~= 33 million. The article goes into some detail why considering Turing machines that quasi halt instead of strictly halting provides some insight into some interesting questions, notably the spaghetti code conjecture.
- SilasX 5y agoHm, that reminds me -- the convention in the nand2tetris course (where you virtually build a computer and OS from circuit) was that your programs don't halt either, at the level of the machine code, you just send them into a (small) infinite loop.
- dandanua 5y agoThey just showed that QQ(4)>32mil, the exact value is still not known. And that function L is a "champion" only in comparison to other functions checked by them. Proving the exact value of QQ(4) could be impossible in standard theories. QQ is uncomputable, afterall.