Number of 5-state machines

I noticed on https://bbchallenge.org/method you guys list 125,479,989 total machines and 34,104,723 halting. For what it’s worth, using our code we enumerated 126,891,605 total machines and 34,358,413 halting. Of course, these counts can very a little bit depending upon the precise details of how you are doing TNF and if you added in any shortcuts, but our numbers are soooo close, it makes me wonder if you might have missed any somehow (maybe because of your space limit?).

If you’re interested in investigating, we have a list of all of our machines in GitHub - sligocki/busy-beaver-data . Look for Enum.5.2.* . Hopefully the format is understandable (I see yours is very similar / almost identical to ours).

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:

  1. 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.

  1. 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!

Aha, we do not do either of those pruning steps. I can certainly imagine that that could be the difference. Some of your pruned machines are halting, so it could explain that discrepancy as well.

However, now I see that you have a precise number of such pruned machines and that it is bigger than the difference between our counts! Did you include these “pruned” machines in the seed, but not their children? Still some mysteries to explore.

I agree that it is a bit unlikely that a TM with 2 undefined transitions would cover more tape than Marxen’s champion, so that theory is not very likely.

Yes, both pruned machines and their successors were NOT included in the seed (the successors were not even enumerated).

This logic happens in that condition: bbchallenge-seed/enumerate.go at 9eda3e6b735f618004c76466c9a239f83f4e22fe · bbchallenge/bbchallenge-seed · GitHub

The continue prevents the machine from being simulated or logged:

Simulation: https://github.com/bbchallenge/bbchallenge-seed/blob/9eda3e6b735f618004c76466c9a239f83f4e22fe/lib_bbchallenge/enumerate.go#L150

Log: https://github.com/bbchallenge/bbchallenge-seed/blob/9eda3e6b735f618004c76466c9a239f83f4e22fe/lib_bbchallenge/enumerate.go#L203

Note the unrelated fact that we know, by their position in the DB, whether a machine exceeded the space or the time limit (index is < 14,322,029 if time limit of 47M was exceeded otherwise 12K space limit was exceeded, hence most machines exceeded the space limit rather than the time limit, as expected).

I finally got around to downloading your list of seed machines and converting to my format to compare against my list. Your list is strictly a subset of my list. Of the ones I have that you don’t most seem to be either:

  1. 4 states or fewer utilized
  2. 2 states which can be identified without changing behavior.
  3. This 2nd pruning condition which was less obvious to me. Ex:
1RB ---  0LB 0LC  0LD 0RD  0LE 1LE  ??? ???

I guess the idea here is that for any machine like this, C1 -> 0RD can be replaced with whatever E1 -> and you will get a machine which has the same eventual behavior (and ending tape). Of course that other TM might have much longer runtime as it does 3 steps instead of 1 when doing C1 trans.

Thank you very much for going through the effort of doing this, I have not had the time yet to do the same in the other direction. It’s good news that we are a strict subset!

  1. Yes, we used BB(4) = 107 to decide machines that use less than 4 states and run for 108 steps
  2. and 3. Yes, we use the pruning rules described in [Marxen & Buntrock, 1990] (Section 3, look for “There are further equivalence classes of medium importance, e.g:”).

The second pruning rule works as follows: it detects transitions that waste one move going to the adjacent cell without modifying its content and directly coming back to the same position (such as your 0LE 1LE). Since, the position has not changed we can skip that transition and directly go to its target state, exactly as you said.

There were very few machines pruned altogether (~900,000) and, although, it also removed their descendants, retrospectively, it was maybe a bit dangerous to implement the pruning rules because, as they are a tiny bit subtle, they could be bugged which would compromise the seed. I hope they are not!