Closed state/transition cluster

Deciders
1

closed state/transition cluster: caught in a range of states

This decider does not correspond to a “family”, since it does describe the TMs future operation only by the states, and ignores the tape contents completely.
In mabu90 we have:

If there is a set S of states such that all transitions from elements of S are defined and their target state is also in S, (and the machine is in one of these states) it will never again leave S and thus not halt (closed state/transition cluster).

Currently (2022-07-10) I miss it from the collection of deciders. Since in 1990 it were important (and very efficient), I would think its omission should have an explicit explanation.

Decider examples and counterexamples

  • Examples: #4 #9
  • Counterexamples: #5

Decider code

Informally: we scan the states s of the TM downwards, fail if one of the transitions of s is not defined, compute the lowest target state occurring in the transitions of s, and succeed, when s <= (that minimum).

Decider tests

NYI

Results

That some of the TMs in question are (Translated) Cyclers, does not come as a surprise to me. That some of them are decided by “Backward reasoning” does come as a surprise.

Now, that I have thought about it, I suspect “Backward reasoning” to catch most of the TMs in question. But I am not sure about this… what do you think about it?

Database subset of application

NYI

Decider correctness
NYI

2 Likes
2

I would guess that backwards reasoning would decide all of the cases a decider for the closed state/transition cluster would, as they operate with similar reasoning (prove getting to the halt state is impossible).

The only way a backwards reasoning test wouldn’t pick it up was if there was a way to “reverse” the Turing machine while still avoiding the closed loop. It seems unlikely to me that this would ever happen for a non-halting machine.

3

Thank you for your post!

I agree that this decider is missing. I will implement it soon!

Thank you again,

1 Like
4

I programmed the decider and applied it to the currently 1,538,612 undecided machines.

It decided 5,647 machines and this has been verified independently by @Iijil

Here are those machines: https://github.com/bbchallenge/bbchallenge-deciders/blob/decider-closed-states/decider-closed-states/output/machines-closed-states.csv

And here the code, which I made in Python as it is a very lightweight decider (you don’t even need to run the machines): Decider closed states by tcosmo · Pull Request #10 · bbchallenge/bbchallenge-deciders · GitHub

A tiny proof is drafted in the comments of the decider as of why you don’t have to run the machines to conclude:

If the machine ever enters a closed set of states where
all transitions are defined, then it never halts.

Note that by:

1. By construction, any state of a machine of bbchallenge that
contains at least one defined transition has been reach at some point in the
execution of the machine.

2. Furthermore, there are no machines in the db with a state that has 2 undefined transitions,
since this is solved by BB(4) = 107 during enumeration. This means that with point 1. we know
that all the states of the machine are reached at some point by the machine when started from
blank tape.

Hence we don't need to run the machine at all, but we just need to check its code to see if there
exists such a closed set of states where all transitions are defined. We know that it'll be reached
and that the machine does not halt.

`

Any reviews or comments are welcome!

1 Like