Machines with more than 1 undefined transition

@modderme123 made the important observation (in this original thread) that if we only care about finding BB(5) then there is no need to study machines that have 5 states but more than 1 undefined transitions.

This is because BB(5) = BB(5 states and 1 undefined transition) >= BB(5 states and 2 undefined transitions) >= BB(5 states and 3 undefined transitions) >= … >= BB(5 states and 5 undefined transitions) since for instance a machine with 1 undefined transitions can in particular simulate a machine with 2. If you go to more than 5 undefined transitions then you lose a state and drop to BB(4).

There are such machines in the seed database, e.g. Machine #13,009,381. I believe that they could be placed in a new category (different from decided/undecided) that could be called “irrelevant” (if you have a better name…) as they are irrelevant when it comes to BB(5). However they are relevant if you want to study BB(5 states and x undefinied transitions) with 1 < x <= 5.

At the day of writing this post there are 3,574,222 undecided machines and among them 159,045 have more than 1 undefined transition. More precisely:

  • 155,500 have 2 undefined transitions
  • 3,545 have 3 undefined transitions

Find here the 3,545 ids of the machines that have 3 undefined transitions. Deciding them all would give the value of BB(5 with 3 undefined transitions). Note that we could already compute BB(5 with x undefined transitions) with x = 4 and x = 5 since there are none of these in the remaining undecided machines.

First few of these 3,545 currently undecided machines with 3 undefined transitions: [9, 11, 30, 49, 75, 77, 99, 162, 163, 164, 207, 208, 210, 211, 214, 216, 222, 236, 237, 238, 239, 240, 241, 242, 243, 245, 253, 254, 274, 275, 276, 277, 278, 324, 345, 354, 355, 375, 381, 384, 391, 395, 396, 397, 404, 753, 861, 961, 967, 1107, 1114, 1115, 1179, 1323, 1451, 1512, 1579, 1837, 1852, 3476, 3478, 3650, 4190, 4191, 4918, 4919, 5138, 5942, 5947, 5964, 5981, 5986, 6002, 6090, 6105, 6138, 6251, 6252, 6253, 6254, 6270, 6271, 6273, 6284, 6305, 6307, 6313, 6346, 6347, 6348, 6374, 6377, 6398, 6411, 6417, 6528, 6529, 6581, 6582, 6586, 6592, 6711, 6721, 6722, 6744, 6745, 6758, 6908, 6914, 7330, 7605, 7606, 7712, 7714, 7769, 7770, 7771, 7905, 8277, 8343, 8374, 8568, 8571, 8644, 8645, 8646, 8647, 9082, 9167, 9485, 9759, 10526, 10527, 10528, 11979, 11980, 11981, 11984, 11987, 12010, 12041, 12042, 12047, 12054, 12069, 12098, 12099, 12100, 12121, 12131, 12145, 12146, 12147, 12149, 12150, 12152, 12172, 12173, 12174, 12175, 12176, 12280,...

I just realized that the seed database as it is constructed currently will likely not allow us to solve one problem above, because we expect BB(5)≥BB(5 states and 2 undefined transitions), and we drop all machines less than the current BB(5) champion, so the BB(5 states and 2 undefined transitions) is likely not in the seed

You would “just” need to re-run a slightly modified version of https://github.com/bbchallenge/bbchallenge-seed where you’d record along the way those (5 states and 2 undefined transitions)-machines that meet one of the undefined transition after more time than you saw before.

This would give you a pretty good estimate of BB(5 states and 2 undefined transitions).

Running https://github.com/bbchallenge/bbchallenge-seed takes roughly 30 hours when ran in parallel on 4 good spec computers.