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.
Bug 1:
Pruned machines are not counted towards the total number of enumerated machines. The check for pruning happens before localNbMachineSeen is incremented.
Bug 2:
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.