3 ms·
The 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 ma
by Kranar 5y ago
The 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.