Hacker News new | ask | show | jobs
by csl 3341 days ago
If anyone is interested, I attempted to plot the first few Busy Beaver iterations: https://github.com/cslarsen/busy-beaver
1 comments

>Busy beaver machines are, by definition, non-halting machines

Is this an error? I thought busy beaver must halt?

Thanks, 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.