Can we really discard machines after 107 steps if they have only visited four states?

Let’s assume that BB(4) is really 107. This means that among all four-state machines that include a Halt state, none of them halts after more than 107 steps. But the four-state machines that are being discarded don’t generally include a Halt state among those four, unless I have misunderstood the description of the Seed Database construction. This gives them more scope! So a machine might run conceivably run for more than 107 steps, visiting only states A-D, and then transition to state E, after which anything can happen.

Or am I missing something obvious?

I misunderstood your question sorry, I will come back to it at a later time.

I misunderstood your original question sorry, I will come back to it at a later time. One note though is that there no such things as “halting state”, only halting transitions.

Point taken! Please mentally replace all occurrences of “Halt state” with “halting transition”.

1 Like

Assume a machine stays in states A-D for BB(4) steps.
Make a 4-state TM with the same transitions where possible, but with transitions to any non-A-D state replaced with a halt.
Then the first BB(4) transitions of the original machine are the same in the new one, so the new one also takes BB(4) steps without halting, so the new one runs an infinite sequence of non-halting transitions (necessarily copied verbatim from the original), so the same sequence is a valid trajectory for the original.

1 Like

Thank you! I am persuaded.

2 Likes