Shift overflow counter

Shift overflow counter is an informal class of Turing machines. A typical Turing machine in this class has the following behavior:

• it represents digits as short fixed-length blocks of symbols
• it spends most of its time implementing basic double counter until one of the sides overflows (expands) which leads to changing the offsets of blocks, making them non-valid representations of digits
• after “Counter Phase” there is a “Reset Phase” where the contents are “reparsed”, creating a new double counter configuration. The new configuration could lead to halting.

Note: some examples (like the Halthing shift-overflow counters below) use a counter on one side and a bouncer (sometimes called unary counter) on the other.

Examples

• Skelet holdouts: Skelet 34, Skelet 33, Skelet 35, Skelet 15, Skelet 26
• 1RB1LD_1RC0RB_1LA0LE_1LC0LA_1RZ1RB (bbch)
• 1RB0RF_1LC1RB_0RD0LB_---0LE_1RE0RA_1RD1RE (bbch)
• 1RB1LD_1RC0RB_1LA1LE_1LC0LA_1RZ0RD (bbch)

Halting shift-overflow counters:

• Current longest running BB(2,5) TM: 1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ (bbch)
• Current fifth longest running BB(6) TM: 1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA (bbch)

Related links

• Skelet #34 is Infinite
• Shift Overflow Counters
• Skelet #26 and #15 do not halt - Coq proof
• Skelet #34 and #35 – Coq proof
• Skelet #33 doesn’t halt - Coq proof