This has been discussed on Discord already. For better discoverability I’m making this forum post.
I have reproduced the seed database. I get the same set of undecided machines. I do not get the same enumerated machine counts as the Method page. This has been written up on Github .
Here is a copy of the issue.
Pruned machines are not counted towards the total number of enumerated machines. The check for pruning happens before
localNbMachineSeen is incremented.
Task division counts root level machines several times. For a TaskDivisor of N, every one of the N runners will count all the IsRoot=true machines. But they should have been counted only once. This happens because the task check is done after
localNbMachineSeen is incremented. This leads to overcounting of (N-1) * 8 = 24.
8 comes from the possible choices for the first undefined transition. There are 2 symbols, 2 head move directions and 2 state choices.
Together these bugs explain the wrong total enumerated machine count on the website. The website lists
halt = 34104723 run_forever = 2711178 pruned = 944579 undecided = 88664064 enumerated = 125479989
I noticed that the final number does not add from the previous ones. We can now explain this:
duplicate_enumerated = 24 # Not adding pruned (halt + run_forever + undecided + duplicate_enumerated) == enumerated > True correct_enumerated = halt + run_forever + pruned + undecided correct_enumerated > 126424544
Next, there is a discrepancy with the results I obtained from my reproduction of the seed run. I almost get the same results as in the previous section. Except that my run_forever is 12 smaller than the seed’s. This is explained by the same Bug 2. The task divisor check only happens in the halting case. It does not happen in the run-forever case. This means that root machines that run forever are also overcounted. After the first 1RB transition these are the possible choices for the transition to define state B reading symbol 0:
0LA halt 1LA halt 0RA loop 1RA loop 0LB halt 1LB halt 0RB loop 1RB loop
4 of these lead to running forever (loop). For a task divisor of 4 these are counted a total number of 4 * 4 = 16 times but should have been counted only once. 16 - 4 = 12 which explains the discrepancy.
The correct counts are:
- halt: 34104723 (as before)
- run forever: 2711166 (12 less than before)
- undecided: 88664064 (as before)
- pruned: 944579 (as before)
- total: 126424532 (sum of previous)
My code can be found here https://github.com/e00E/busy-beaver/tree/master/crates/seed . It has some advantages over the original seed run implementation. They are described in the Readme.