Waw! Crazy that the numbers are so close!
Thank you for taking the time to check on these details.
In case it is not clear let me just add the precision that the database that we share at https://bbchallenge.org/method#download contains only the undecided machines: 88,664,064 machines. Unfortunately, I have not saved each of the 125,479,989 enumerated machine. (Although it would “just” take 30h on 4 computers to get that list).
About the 2 discrepancies:
- We enumerate 125,479,989 VS you enumerate 126,891,605: I can see only two reason why these numbers would be different (assuming there are no bugs, which is a very strong assumption alright).
(a) as you mentionned, we have a memory limit of 12,289 memory cells as we conjecture that BB_space(5) = 12,289. If that conjecture was false because of a machine M with more than one transition left to define, we would not have visited its subtree of machines. This would mean that some machine with at least 2 undefined transitions of the undecided DB is in fact halting and we will discover that down the road when studying this machine. I personally do not believe that a machine with 8 transitions could beat 12,289 memory cells, but who knows!
Note that the conjecture BB_space(5) = 12,289 might still be false among the machines with 9 transitions, but in that case no machine can have been missed in the enumeration because of that. Indeed, such machines have an empty subtree in any case because defining their last transition as non-halting would trivially make any children be non-halting as… they have no halting transition.
(b) We have used 2 pruning arguments (orginally presented in Marxen&Buntrock) that allowed us NOT to visit the subtrees of 944 579 machines: bbchallenge-seed/prune.go at main · bbchallenge/bbchallenge-seed · GitHub. If you have used slightly different pruning arguments this could explain the discrepancy.
- We marked 34,104,723 as halting VS you marked 34,358,413 as halting. Two similar possible reasons:
(a) Conjecture BB_space(5) = 12,289 might be false, hence we might currently have in the undecided DB machines that actually do halt. Hopefully we should discover them soon. A very simple way to do so will be, when we get let’s say < 200k undecided machines to run all those 200k machines for 50M steps. These machines cannot hide for too long. That will update the conjecture which is cool! Note that 12,289 is the number of cells visited by M&B BB5 champion, would be funny if the time and the space champions were different.
(b) If you visited some of the subtrees that we pruned, you will have encountered more internal nodes than us, which are halting machines.
It is super important to me that we get to the bottom of this discrepancy, and I will investigate further in the months to come. I opened an issue: Understand the discrepancy with Shawn Ligocki's results · Issue #2 · bbchallenge/bbchallenge-seed · GitHub
Thank you again!