Machines with more than 1 undefined transition

Deciders
1

@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,...

4

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

5

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.

6

Reported by @mateon1 here is the number of machines with x undefined transitions on the entire seed db:

81467837 machines have 1 undefined transition
6772809 machines have 2 undefined transitions
405008 machines have 3 undefined transitions
18000 machines have 4 undefined transitions
410 machines have 5 undefined transitions
7

If you enumerate all machines, then indeed, you only need to care about those with one transition. But I think a better approach would be to prune in the other direction – if a Turing machine with two halting transitions doesn’t seem to be halting, you can disregard all machines you can construct by filling out the halting transitions. This would save much more processing.

In fact, if I understand correctly, this is the approach taken by the seed database construction algorithm. In that case, discarding the machines you’ve called “irrelevant” would be unsound.

8

That’s indeed what happens in the seed DB :slight_smile: