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, and we exclude halting machines. 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 TNF-1RB machines with 2 states and 2 symbols, with the following breakdown:

Classification	Count	Notable examples
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
Cycler	14	1RB0RB_1LB1LA (bbch), one of the 7 TMs with a record period of 4 1RB1LB_1LA1RA (bbch), unique TM with record preperiod of 5
Bouncer	3	1RB1LA_0LA1RB (bbch) 1RB1LA_1LA1RB (bbch) 1RB0LB_1LA0RA (bbch)
Counter	1	1RB1LA_0LA0RB (bbch), a binary counter.

3 × 2

There are 15,064 TNF-1RB machines with 3 states and 2 symbols, with the following breakdown:

Classification	Count	Notable examples
Translated cycler	12,427	1RB0LA_0RC1LA_1LC0RB (bbch), unique TM with a record period of 92 1RB1LB_0RC0LA_1LC0LA (bbch), unique TM with a record preperiod of 101
Cycler	1,969	1RB0LB_1LB1LC_0RC1RA (bbch), unique TM with a record period of 18 1RB1RC_1LC0LB_1RA1LA (bbch), unique TM with record preperiod of 22
Bouncer	558	1RB0LC_1RC0RB_1LA1LC (bbch), a bouncer with two distinct shift rules.
Counter	95	1RB1LA_0LA0RC_0LA1RB (bbch), a Fibonacci counter. 1RB1LA_0LA1RC_0LA0RB (bbch), a two-phase binary counter. 1RB1LA_0LA1RC_1LB0RB (bbch), a binary bi-counter.
Cubic bell	10	1RB1LA_0LA0RC_0LA1RC (bbch), a typical cubic bell.
Bell	5	1RB0LC_1RC1RA_1LA0RB (bbch), a typical bell. 1RB1LA_0RC0RC_1LC0LA (bbch), a typical inverted bell.

4 × 2

There are 2,744,516 TNF-1RB machines with 4 states and 2 symbols, with the following breakdown. This breakdown is not complete due the fact that there are still some unclassified Turing machines.

Classification	Count	Notes and Notable examples
Translated cycler	≥2,253,849	1RB0LA_0RC1RD_1LD0RB_1LA1RB (bbch), the current period record holder, with a period of 212,081,736. Before phasing into a translated cycle, this machine appears to be a spaghetti. 1RB1LC_0LA1RD_0RB0LC_1LA0RD (bbch), the current preperiod record holder, with a preperiod of 119,120,230,102. Before phasing into a translated cycle, this machine appears to be a spaghetti.
Cycler	≥341617	1RB0RB_1LC0RD_1LA1LB_0LC1RD (bbch), likely period record holder, with a period of 120. 1RB1LB_1LC1RD_1LA0RD_0LA0RB (bbch), likely preperiod record holder, with a preperiod of 146.
Bouncer	≈132,000	1RB1LA_1LC0RC_0RA1LD_1RC0LD (bbch), the current record holder for longest time to settle into a bouncer, with a start step of 83,158,409. 1RB0RC_0RC0RB_1LC0LD_1LA0RA (bbch), starts out as irregular-side bells before phasing into a bouncer at step 3350. 1RB1LC_0RD0LC_1LB0LA_1LD1RA (bbch), a bouncer with very complex runs. Start step 145,729.
Counter	≈14,700	1RB1LA_0LA0RC_0LA0RD_0LA1RC (bbch), a counter encoding a recurrence with characteristic polynomial $x^{3}-x^{2}-2x+1$. 1RB1LA_0LA0RC_0LA1RD_0LA0RB (bbch), a counter encoding a recurrence with characteristic polynomial $x^{3}-x^{2}-2$. 1RB1LC_1LD1RA_0RA0LC_0RB0LD (bbch), a counter encoding a recurrence that grows like $n\cdot 2^{n}$. 1RB0RC_0LC0RA_1LA0LD_1RA1LD (bbch), a tri-phasic binary counter. 1RB1LC_0RD0RB_1LA0LA_1LD0LA (bbch), an example of a superexponential counter.
Bell	≈2,350	1RB1LA_0RC0LD_1LC0LA_1RC0RD (bbch), a typical inverted bell. 1RB1LB_1LC0RA_1RD0LB_1LA1RC (bbch), alternates between bell and half-bell. 1RB0LC_1RC1RB_1LA1LD_0RA0RB (bbch), a grow-and-shrink bell. 1RB0RC_1LC0RA_1RA1LD_0LC0LA (bbch), starts out as an irregular bell before phasing into a bell.
Cubic bell	≈1,376	1RB1RC_1LC0RC_0RA1LD_0LC0LB (bbch), a cubic inverted bell. 1RB0RC_0LD0RA_0LA1RC_1LA1LD (bbch), a cubic grow-and-shrink bell.
Bouncer + X	≈365	1RB1LA_1RC0RB_0LC1LD_0LD1RA (bbch), a bouncer + binary counter. 1RB0LA_0RC1LA_1RD0RA_0LB1RB (bbch), a bouncer + bell. 1RB1LC_0RC1RD_1LA0LA_1RC0RB (bbch), a bouncer + cellular automaton. This could be universal. 1RB1LC_0RC1RD_1LA0LA_0LA0RB (bbch), a bouncer + cellular automaton with a fractal nature. 1RB1LB_0LC0RD_0RA1LC_1RA1RD (bbch), a bouncer + cubic bell, leading to quartic tape growth on the left. 1RB1LA_1RC0RB_0LC1LD_0LD1RA (bbch), a bouncer + binary counter. 1RB0LC_1LA1RD_1RA1LD_0LA0RB (bbch), a bouncer + unclassified. (If you can classify it, let me know in the talk page!)
Bouncing counter	≈330	1RB1LC_1LC0RB_1RA0LD_1RA1LA (bbch), a typical bouncing binary counter. 1RB1LB_1RC1RD_0LA0RC_1LD0LB (bbch), a typical bouncing quaternary counter. 1RB1RA_0RC0LC_1LA0LD_0RA1LC (bbch), a bouncing ternary counter, which is more rare. 1RB0LA_0RC1LA_0RD1RB_1LD1LA (bbch), a hybrid quaternary-octal bouncing counter. 1RB0LC_1RD0RB_1LA1RC_1LC1RB (bbch), a bouncing 3/2-counter. 1RB0LC_1LC0RD_1RA1LA_0RA0LA (bbch), a bouncing binary counter with stationary counter digits.
Irregular bell	39	1RB0RC_1LC1RA_1RA1LD_0LC0LA (bbch), a typical irregular bell. 1RB1LA_0RC0RD_1LD1RC_1LD0LA (bbch), a typical irregular inverted bell.
Fractal	20	1RB1RC_0RC0RB_0LD1LA_1LD0LA (bbch), a typical example.
Tetration counter	19	1RB1LC_0RD0RD_0RC0LA_1LD1RA (bbch), a typical example.
Cubic bouncing counter	13	1RB1RA_0LC0RB_0RA0LD_1LC1RD (bbch), a typical example. Note that these share many of the same properties as dekaheptoids.
Spaghetti	26	This is an informal description for spaghetti-code Turing machines that seem to have no predictable behavior, instead winding back and forth like a spaghetti. Any of these machines could potentially end up proven as one of the above classifications. 1RB0RB_1LC1RC_0RA1LD_1RC0LD (bbch), a typical spaghetti. 1RB0RA_1RC0RD_1LD1LC_1RA0LC (bbch), a spaghetti that seems to converge to a bouncing counter. 1RB1LC_0LA0RD_1LA0LB_1LA1RD (bbch), a spaghetti whose envelope seems to converge to that of a bouncer. 1RB0RC_1LC1LD_1RD1LB_1RA0LB (bbch), a cellular-automaton-like bouncer. The spaghetti nature of this machine is local. 1RB1LC_1LA1RD_1RA0LC_1LB0RD (bbch), a "spaghetti sandwich" -- a spaghetti sandwiched on the left and right by a growing predictable repeating pattern.
Chaotic counter	10	Chaotic counters have slow-growing tapes like counters, but the behavior seems to be chaotic and is as of yet unknown: 1RB0RC_0LD1RC_1LD0RB_0LA1LA (bbch) 1RB1RA_0LC0LD_1LD0RB_0RA1LC (bbch) 1RB0RC_1LA1RC_0LD0RB_0LA1LD (bbch) 1RB0RB_1LC1RA_1LD0LC_0RA0LD (bbch) 1RB1LA_0RC1RC_0LD0RB_0LA1LD (bbch) 1RB1LC_0LC0RD_0LA1LA_0RB1RD (bbch) 1RB0RB_0LC1RA_1LD1LC_0RA0LD (bbch) 1RB1LC_1LD0RB_1RA0LC_0RA0LD (bbch) 1RB1LC_0LA0RB_1RD0LC_1LA0RD (bbch) 1RB1LC_1RD0RB_1LA0LC_0LA0RD (bbch)

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)