3 ms·
If anyone is interested, I attempted to plot the first few Busy Beaver iterations: https://github.com/cslarsen/busy-beaver https://github.com/cslarsen/busy-beav
by csl 9y ago
If anyone is interested, I attempted to plot the first few Busy Beaver iterations: https://github.com/cslarsen/busy-beaver https://github.com/cslarsen/busy-beaver
- dorgo 9y ago>Busy beaver machines are, by definition, non-halting machines Is this an error? I thought busy beaver must halt?
- csl 9y agoThanks, I see now that the whole section is very clumsily written. IIRC, a Busy Beaver may halt or not. You only care about those that _do_ halt, though, and the _champion_ is the one with the most number of 1s on the tape. The whole problem is determining if a given machine will halt or not. Which we know, by the halting theorem, is possible to prove on a case-by-case basis, but not in the general case (i.e., you cannot create an algorithm to determine it). So you resort to heuristics. E.g., if a machine never has a "go to the halt state" in its transition table, you know that it can't ever halt. But as the machines grow, you'll have to cover an infinite amount of such heuristics, hence the incomputable nature of them.