3 ms·
Is there any intution for why BBB (beeping busy beavers) can run for much longer (before quasihalting?) One thing I see is that they effectively don't need to
by kzrdude 3y ago
Is there any intution for why BBB (beeping busy beavers) can run for much longer (before quasihalting?)
One thing I see is that they effectively don't need to use a halt state. So maybe a 3-state BBB is sort of similar to a 4-state BB in that sense. What is there more to it?
- voidmain 3y agoA program can only halt once, but can beep any number of times. So you can make a size X program (or turing machine) that simulates running every program (or turing machine) up to some size Y >> X, and whenever any of those programs halts it beeps. The last time it beeps will be when it simulates the halting of BB(Y) after more than BB(Y) steps, so BBB(X) > BB(Y) >> BB(X). IIRC basically this same construction means that while knowing BB(N) lets you (very slowly) compute the halting problem for programs up to size N, knowing BBB(N) lets you (even more slowly) compute the halting problem for turing machines supplied with a halting oracle up to that size.