expect machines to only have one undefined transition

[milomg]

WLOG, if a machine halts it will only halt on one of the undefined transitions, so machines with more than one undefined transitions are isomorphic to another machine with only one.

For example: this machine should not be a machine that needs to be decided

[tcosmo]

I believe that the point is more subtle.

Which machine in the database is isomorphic to https://bbchallenge.org/13009381 and has only 1 missing transition? By construction, there is no machine with the exact same content plus 1 transition in the database. So you cannot (at least in a simple way) link this machine directly to another machine of the beasy beaver challenge.

HOWEVER, when it comes to asking what the value of BB(5) is it is true that we do not care about these machines.

This is because BB(5) = BB(5 states with 9 defined transitions) >= BB(5 states with 8 defined transitions). So if you know BB(5) you can use this value to decide the machine with the 2 missing transitions (you will run more steps than is actually necessary but you'll get the answer).

NOW: I feel uncomfortable marking these machines as "decided"... Because they are not. It seems that there is room for a new category on top of decided/undecided that could be called "irrelevant". This would be different from categories called "isomorphic to #xxx" where you'd put machines that are isomorphic to machine #xxx of the database which is also another tool to reduce the set of machines to study.

P.S: It would be an interesting subtask to conjecture and prove the value of BB(5 states with 8 defined transitions) which is an intermediate problem between BB(4) and BB(5).

P.P.S: there is no machine with 0 undefined transition in the databse, which this decider "description_full" was initially meant to check. This was expected because of how the databse is constructed, and this decider acted as a safeguard.

[milomg]

Hmm, then maybe these machines should just be removed from the seed? I expected that the machines there would have some initial isomorphism tests to other machines, which was why I wrote this test.

[tcosmo]

The machines are all unique. What made you think there were repeats in my previous message?

I don't think they should be removed from the seed database. I see the question about BB(5 states with 8 defined transitions) as an interesting problem which is easier than BB(5) and above of the current state-of-the-art BB(4) (hence publishable).

[milomg]

Whoops, just meant to ask whether you wanted the seed to be somewhat minimized for BB(5) isomorphisms or not, but I now understand that is not the case

[tcosmo]

@modderme123 I still believe that the point is interesting and that there could be a special category for these machines.

In the current 3,574,222 undecided machines there are 159,045 machines that have more than 1 undefined transitions, more precisely:

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

Find attached 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. I opened the discussion here: https://discuss.bbchallenge.org/t/machines-with-more-than-1-undefined-transition/44

undecided_ids_3_undefined_transitions.txt