Non-halting Turing machine

A non-halting Turing machine is a Turing machine that does not halt. These include halt-free Turing machines, meaning those without an undefined or halt transition, as well as non-halt-free Turing machines that never enter an undefined or halt transition.

The crux of the Busy Beaver problem for a given n and k is to prove that all non-halting Turing machines are, in fact, non-halting.

The zoology of non-halting Turing machines is extremely rich. See Translated cycler, Bouncer, Bell, Counter, Shift overflow counter, Shift overflow bouncer counter for a sample. In this page, we provide a detailed zoology for some low numbers of states and symbols.

Zoology

Machines are enumerated in TNF-1RB. In particular, a transition is defined if and only if it is reachable; unreachable transitions are undefined. This avoids duplicates.

2 × 2

There are 106 machines total, with the following breakdown:

Classification	Count	Notable examples
Cycler	14	1RB1LB_1LA1RA (bbch), unique TM with record preperiod of 5 1RB0RB_1LB1LA (bbch), one of the 7 TMs with a record period of 4
Translated cycler	88	1RB0RB_1LB1RA (bbch), unique TM with a record period of 9 1RB0LB_1LA0RB (bbch), unique TM with a record preperiod of 9
Bouncer	3	1RB1LA_0LA1RB (bbch) 1RB1LA_1LA1RB (bbch) 1RB0LB_1LA0RA (bbch)
Counter	1	1RB1LA_0LA0RB (bbch), a binary counter.

Partial classification

• Cyclers
• Translated cyclers
• Bouncers (first seen in 2x2)
• Bells
  • Exponential bells (first seen in 3x2)
  • Cubic bells (first seen in 3x2)
  • Quartic bells (first seen in 5x2)
  • etc...
  • Irregular bells
• Counters (first seen in 2x2)
  • Regular
  • Irregular
  • Exponential/tetration...
• Hybrid (counter-counter, bouncer-counter)
• Fractals
  • Cube-like fractals (first seen in 4x2)
  • Christmas tree fractals (first seen in 2x4)
• Spaghetti (first seen in 4x2)
  • Asymptotically parabolically-shaped spaghetti e.g. 1RB0LB_1RC1LD_1LA0RC_0LA1LD (bbch)
  • Asymptotically irregular spaghetti e.g. 1RB0RB_1LC1RC_0RA1LD_1RC0LD (bbch). I suspect most irregular spaghetti, including this example, eventually become translated cyclers.
  • Note: The bbchallenge links cannot show more than 65,536 steps, so it is very difficult to differentiate asymptotic shapes via the above 2 links. See here and here for visualizations of the asymptotic shapes.
• Cellular automata (first seen in 5x2 and 3x3)

Sometimes phase transitions can occur. For example, 1RB1RC_1LC0RA_0LB0LD_1LA1LD (bbch) starts out as an irregular bell but phase transitions into a translated cycler with period 4222 at step 29754825.

An informal argument, in light of the uncomputability of the Busy Beaver function, suggests that there can never be a complete classification of behaviors of Turing machines for arbitrarily high numbers of states.

Records

Translated cycler preperiod

• 3x2: 101 (proven): 1RB1LB_0RC0LA_1LC0LA (bbch) (period = 24)
• 4x2: 119,120,230,102 (current champion): 1RB1LC_0LA1RD_0RB0LC_1LA0RD (bbch) (period = 966,716)
• 2x4: 293,225,660,896 (current champion): 1RB2LA0RA3LA_1LA1LB3RB1RA (bbch) (period = 483,328)

Translated cycler period

• 3x2: 92 (proven): 1RB0LA_0RC1LA_1LC0RB (bbch) (preperiod = 0)
• 4x2: 212,081,736 (current champion): 1RB0LA_0RC1RD_1LD0RB_1LA1RB (bbch) (preperiod = 5,248,647,886)
• 2x4: 33,209,131 (current champion): 1RB0RA3LB1RB_2LA0LB1RA2RB (bbch) (preperiod = 63,141,841)