Dekaheptoid: Difference between revisions

Revision as of 22:37, 7 September 2024

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:

Rightmost digit (denoted by last). The parity of last can be relevant, and is either 0 or 1, as calculated by last % 2. Possible values of last are all natural numbers $\mathbb {N} ={0,1,2,3,...}$ (note, however, that only 0 and 1 values affect the behaviour; everything else could be merged into a single class named 2+)
Gray code value (denoted by grayval): the integer corresponding to the Gray code bitstring obtained by calculating the parity of each number (except the last) in the list. For a list of length $L$ , possible Grey code values are $[0,1,2,...,2^{L}-1]$ . If grayval == 0, all entries in the list are even, except perhaps the last one. If grayval == 2^L - 1, all entries in the list are odd, except perhaps the last one.
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 1RB---_0LC1RF_0LE1LD_0RD1LC_1RA1LB_0RB0RA (bbch) 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 (based on 1RB---_0LC1RF_0LD1LC_1RE1LB_1RD0RB_0RB0RA)

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 -- an overflow variant (see below)

grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "2+" :
 apply_zero_D -- an overflow variant (see below)

grayval == '2^L - 1' and L == 1:
apply_leading_zero_increment o apply_add_one_zero o apply_overflow -- increment the leading digit, add leading zero, then add one leading zero, then increase the first non-zero digit and decrease the last digit.

grayval == "0" and ((internal_zeros_len > 0) or (num_ending_zeros > 2) or (num_leading_zeros > 0)) :
 apply_halt

if the halting condition isn't met, then the either of these ones happen:
grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 0 :
apply_leading_zero_increment o apply_add_double_zero -- add two leading zeros, then increase the first non-zero digit and decrease the last digit.

grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros > 0 :
 apply_halve o apply_leading_zero_increment o apply_add_double_zero -- the same as above but delete the last digit afterward

The apply_zero_D operation could be written as apply_increment_1N o apply_overflow: increment the leading digit, add leading zero, then increase the first digit (newly added zero) and decrease the last digit.

"Iralic Orcora" family

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

Rules (based on 1RB---_0RC1RF_0LD1RF_0LE1LD_1RA1LC_0RC0RA)

grayval == '2^L - 1' and L == 1:
 apply_init -- increment the only digit and add leading zero
`gray-adic` == "2^L - 1" and rightmost_odd_idx == 0 and last == "2+" :
 apply_zero_increment -- increase the first digit by 2 (instead of more customary 1), add leading zero, decrement the last digit
last == "2+" and rightmost_odd_idx > 0 :
 apply_increment
last == '1' and grayval != '2^L - 1' and grayval != '0' :
 apply_halve_and_increment o apply_increment -- apply the usual Gray Code increment, then delete the last digit and increment the new last digit by 1.
grayval == "0" and last %2 == 0 and ((internal_zeros_len == 0 and num_leading_zeros > 1) or internal_zeros_len > 0 or num_ending_zeros >= 3) :
 apply_halt

if the halting condition isn't met, then the either of these ones happen:

grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 0 :
 apply_zero -- increment the first digit, decrement the last digit, add two leading zeros
grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 1 :
 apply_halve o apply_zero -- increment the first digit, decrement the last digit, add two leading zeros, erase the last digit (that is less than zero now)
grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 2 :
 apply_weird_halve_zero_variant -- erase two last digits (that are zero), increment the first digit and the new last digit, add two leading zeros

"Olaile Orcorb" family

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

Instead of a single Gray Code Increment, these TMs have two different increment rules: Excluding Increment and Shallow Increment. One can also analyze them as a traditional Gray Code Increment except with the parity of last digit switched. Rules (based on 1RB1LC_1RC---_0LD1RF_0LE1LE_0LA1LE_0RC0RB)

last == "0" and rightmost_odd_idx_alt != -1 and rightmost_odd_idx != 0 :
 apply_halve o apply_increment
last != "0"  and rightmost_odd_idx_alt > 0 and last %2 == 1 :
 apply_excluding_increment
last == "2+" and last %2 == 0 :
 apply_shallow_increment

grayval == "0" and all_even == 0 :
 apply_zero
grayval == '2^L - 1' and L > 1 :
 apply_overflow o apply_zero_increment
rightmost_odd_idx_alt == 0 and last == '1' :
 apply_overflow o apply_zero_increment

grayval == "0" and last == "0" and ((`L %2` == 0 and num_ending_zeros == L) or (internal_zeros_len > 0) or (internal_zeros_len == 0 and num_leading_zeros != -1 and (num_leading_zeros >= 3 or num_ending_zeros >= 3))) :
 apply_halt

if the halting condition isn't met, then this rule applies:

L > 1 and grayval == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros > 0 :
 apply_halve o apply_zero

1RB1LC_1RC---_0LD1RE_0LA1LD_0RC1RF_0LF0RB

The rules aren't complete.

last == "0" and rightmost_odd_idx_alt != -1 and rightmost_odd_idx != 0 :
 apply_halve o apply_increment
last != "0" and rightmost_odd_idx > 0 :
 apply_increment
num_leading_zeros == 2 and last == "0" and all_even == 1 :
 apply_halve o apply_weird_double_zero -- first, add two leading zeros, then increment the last leading zero, then delete the last digit

The conditions for these operations aren't described yet:
apply_zero
apply_halve o apply_zero
apply_zero_variant o apply_smudge_internal_zeros
apply_weird_double_zero o apply_halve_and_increment (a rare operation)
apply_weird_double_zero
apply_halt

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.

1RB---_0LC1RF_0LD1LC_1RE1LB_0RE1LA_0RB0RA

last == "0" and rightmost_odd_idx_alt != -1 and rightmost_odd_idx != 0 :
 apply_halve o apply_increment
grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "0" :
 apply_halve o apply_zero_D
grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "2+" :
 apply_zero_D
last != "0" and rightmost_odd_idx > 0 :
 apply_increment
grayval == "0" and last %2 == 0 and ((internal_zeros_len == 0 and num_leading_zeros > 1) or internal_zeros_len > 0 or num_ending_zeros >= 3) :
 apply_halt

if the halting condition isn't met, then this rule applies:

grayval == "0" and L > 1 and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 0 :
 apply_zero

The condition for this operation isn't described yet:
apply_halve o apply_zero

1RB---_0LC1RF_1RA1LD_0LE1RF_0LC1LE_0RD0RA


1RB---_0LC1RF_1RA1LD_0LE1RF_0LC1LE_0RD0RA 9
grayval == "2^L - 1" and rightmost_odd_idx == 0 and last == "2+" :
 apply_zero_D -- see above for description
last == "2+" and rightmost_odd_idx > 0 :
 apply_increment
last == '1' and grayval != '2^L - 1' and grayval != '0' :
 apply_halve_and_increment o apply_excluding_increment
gray == "0" and `last %2` == 0 and ((internal_zeros_len == 0 and num_leading_zeros > 1) or internal_zeros_len > 0 or num_ending_zeros >= 3) :
 apply_halt

If the halting condition isn't met:
L > 1 and gray == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 0 :
 apply_zero
L > 1 and gray == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 1 :
 apply_halve o apply_zero
L > 1 and gray == "0" and internal_zeros_len == 0 and rightmost_odd_idx == -1 and rightmost_odd_idx_alt == -1 and num_ending_zeros == 2 :
 apply_weird_halve_zero

The conditions for these two very rare operations aren't described yet:
apply_weird_incrementing_halve
apply_halve_and_increment o apply_zero_D

1RB---_0RC1RB_1LD1RE_1LE---_0RB1LF_0LE0LD

1RB1LC_1RC---_0LD1RE_0LA1LD_0RF0RB_0LC1RE

This TM is notable, as I was unable to found any config where it would halt.

last == "0" and (rightmost_odd_idx <= 0) and grayval != "2^L - 1" and num_leading_zeros != 2 :
 apply_halve_and_increment
last == "2+" and last %2 == 0 :
 apply_shallow_increment
last == "2+" and last %2 == 1 and gray != "0" :
 apply_excluding_increment
last == "2+" and last %2 == 1 and gray == "0" :
 apply_zero
grayval == '2^L - 1' and L > 1 :
 apply_halve o apply_weird_one_zero o apply_increment_D_even o apply_weird_double_zero
last == '1' and grayval == '0' :
 apply_smudge_internal_zeros o apply_zero
rightmost_odd_idx_alt == 0 and last == '1' :
 apply_halve o apply_weird_one_zero o apply_increment_D_even o apply_weird_double_zero

The conditions for these operations aren't described yet:
apply_weird_incrementing_halve o apply_halve
apply_smudge_internal_zeros o apply_unsafe_increment_1N
apply_halve o apply_increment o apply_excluding_increment

1RB1LC_1RC0RF_0LD1RE_0LA1LD_0RC0RB_0RE---