Dekaheptoid

Dekaheptoid (from Ancient Greek word meaning "seventeen") is an informal class of Turing machines that are, in some sense, similar to Skelet 17. A typical Turing machine in this class has the following behavior:

• it works with the sequence of numbers encoded as $10^{k}$ (here referred to as digits).
• it spends most of its time performing an operation that could be described as incrementing/decrementing the Gray Code of the sequence
• it has a roughly cubic growth rate

The specifics can differ, but some of common tape transformations and conditions are:

• Increment: the value at the last index is decremented and some other value is incremented. Typically this does not expand the tape.
• Halve: the last digit (typically having a value 1 or less) is deleted.
• Zero: expand the tape to the left by adding some number of leading zeros. The leftmost digit could be incremented by some small value. Typically this occurs when all digits (possibly, except for the least significant one) are even.
• Overflow: incrementing the leftmost digit creates new leading zeros.
• Smudge: if an "internal" (i.e. neither the first nor the last) digit is zero, increment it and decrement some digit next to it. In some cases, this leads to halting.

State variables

It is useful to consider the following state variables:

• Least significant digit (denoted by last). The only values of note are $0$, $1$, $2+$ (every digit is odd), and everything in-between. In some cases the parity of that digit will also be relevant (denoted as

  last % 2 == 0

  ).
• Gray Code value (denoted by grayval): the integer that is obtained by calculating the parity of each number (except the last) in the list, considering the result as a Gray Code bitstring corresponding to some integer and "recovering" this integer. The only values of note are $0$ (every digit is even, maybe except for the last one), $2^{L}-1$ (every digit is odd), and everything in-between.
• Number of internal zeros (denoted by num_internal_zero).
• Number of leading zeros (denoted by num_leading_zeros).
• Rightmost odd index, including the last digit (denoted by rightmost_odd_idx). If all entries are even, it is defined as $-1$ by convention.
• Rightmost odd index not counting the last digit (denoted by rightmost_odd_idx_alt). If all pertinent entries are even, it is defined as $-1$ by convention.

Note that if grayval == 0, then rightmost_odd_idx_alt == -1, and rightmost_odd_idx is either 0 or L.

5-state dekaheptoids

Two notable machines are Skelet 17 and 1RB1LC_1RC---_0LD1RE_0LA1LD_0RC0RB (bbch) which is equivalent to Skelet 17 starting from the state D and halts after 533 steps (29 rule applications).

6-state dekaheptoids

Known dekaheptoids fall into one of 12 equivalence classes (based on checking configurations after each rule application; two TMs are considered equivalent if their high-level configs are always equivalent during 15k+ high-level steps).

equivalent to skelet 17

1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0LF_0RA1RF
1RB1RF_0LC1RE_0LD1LC_1RA1LB_0RB1LA_---0RA 
1RB1RF_0LC1RE_0LD1LC_1RA1LB_1LA0RA_---0RB
1RB0RA_0LC1RE_0LD1LC_1RA1LB_0RB1RF_0LA--- 
1RB---_0LC1RF_0LD1LC_1LE1LB_0RE1RA_0RB0RA 
1RB---_0LC1RE_0LD1LC_1RA1LB_0LF0RA_0RB1RF
1RB---_0LC1RF_0LE1LD_0RD1LC_1RA1LB_0RB0RA 
1RB---_0LC1RE_0LD1LC_1RA1LB_0RB1RF_0LF0RA 
1RB---_0LC1RF_0LD1LC_1RE1LB_0LE1RA_0RB0RA 
1RB---_0LC1RE_0LD1LC_1RA1RF_0RB0RA_0LF1LB 

The notable machine is [1] that employs a different mechanism for keeping track of parity.

"Old Relif Orbora" family

1RB---_0LC1RF_0LD1LC_1RE1LB_1RD0RB_0RB0RA 
1RB---_0LC1RF_0LD1LC_1RE1LB_1RD0LB_0RB0RA 
1RB---_0LC1RF_0LD1LC_1RE1LB_1RD0LD_0RB0RA 
1RB---_0LC1RF_0LD1LC_1RE1LB_1RD0LF_0RB0RA 

Rules

last != 0 and rightmost_odd_idx > 0:
 apply_increment -- the usual Gray Code increment operation.
last == 0 and rightmost_odd_idx_alt != -1 and rightmost_odd_idx != 0:
 apply_halve o apply_increment -- first, run an Increment operation, decreasing the last digit to fictitious value "-1"; then, delete the last digit.
last == 0 and (rightmost_odd_idx <= 0) and grayval != "2^L - 1" and num_leading_zeros != 2:
 apply_halve o apply_weird_double_zero -- first, add two leading zeros, then increment the last leading zero, then delete the last digit
For example: [2, 6, 12, 24, 48, 0] -> [0, 1, 2, 6, 12, 24, 48]

grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "0" :
 apply_halve o apply_zero_D -- 
`gray-adic` == "2^L - 1" and rightmost_odd_idx == 0 and last == "2+" :
 apply_zero_D
`gray-adic` == '2^L - 1' and L == 1 :
 apply_weird_one_zero o apply_overflow

"Iralic Orcora" family

1RB---_0LC1RD_0LE1RD_0RC0RA_0LF1LE_1RA1LC
1RB---_0RC1RF_0LD1RF_0LE1LD_1RA1LC_0RC0RA
1RB---_0LB1RC_0RD0RA_0LE1RC_0LF1LE_1RA1LD

"Olaile Orcorb" family

1RB1LC_1RC---_0LD1RF_0LE1RD_0LA1LE_0RC0RB
1RB1LC_1RC---_0LD1RF_0LE1LE_0LA1LE_0RC0RB

1RB---_0LC1LB_1RE1LD_0LB1RF_1RD1RA_0RD0RE

This machine is obtained by adding a new state F to the halting config of Skelet 17. The F state mangles the left end of the tape and introduces a lot of chaos into tape evolution.

2-state, 5-symbol dekaheptoids

The 2LA1RA4LB2LA2RA machine encodes digits as $4^{k}$ separated by $12$. For example, [x,y,z] is represented as $1<B4^{x}124^{y}124^{z}$. Note this machine is mirrored (z is the most significant digit while x is the least significant).

The analysis by @dyuan01 is available here.