Families organized by lowest state appearance

I thought it would be a good idea to organize the different families by complexity, in other words, how many states do you need to demonstrate this behaviour. I will require each example to have a designated halt state (even though they never reach it). This is because another goal of this thread is to test the strength of our current decider system.

1 state

Translated Cyclers
E.g. A1R 1R-

As there can only be one non-halt state in this case, the only non-halting possibility is for a translated cycler.

2 states


E.g. 1RB 0RB ; 0LA 1R-

There still seems to not be that much room for anything more than simple cycles with two states

3 states

Bilateral Bouncers

E.g. 1RB 0LC ; 1LB 1RA ; 1R- 1LA

Exponential Counters

E.g. 1RB 0LC ; 0LA 0RB ; 1LA 1R-

According to the paper from Brady: http://docs.bbchallenge.org/papers/Brady1983.pdf, if deciders for these machines were to be developed and approved, it would be enough to settle BB(3).

1 Like

Thank you for kicking off this effort! Its a very good idea! Great to know what deciding power is enough to settle BB(3).

These machines are indeed the only type of machines that occur in three states. A bilateral bouncer decider and an exponential counter decider are enough to settle BB(3).

I suggest a further distinction of complexity class, the rate of occurrence of different types of machines. This scale should agree with the original classification around how many states are needed to produce a behaviour. It will also allow for a finer distinction.

For example, of the 40 three state Turing machines which are not halting, cyclers, or translated cyclers, 37 are bouncers, while only 3 are counters. According to Brady (see above paper), this same trend continues for 4 state machines, with bouncers occurring more than 10 times as often as counters (unfortunately, Brady does not distinguish bilateral from unilateral bouncers in the paper).

EDIT: I was mistaken, unilateral bouncers do occur in three state machines. Therefore they would need to be included in the three state category.

1 Like