History linear

We call a TM history-linear, iff its transition history (a sequence of (state,read symbol)) can be generated by a program consisting of "output statement" and "for loop".

• Each "output statement" outputs a fixed transition of the TM.

• A "for loop" is like for(int i=0;i<n;++i){...} or for(int i=0;;++i) in C++/Java, where n is an affine expression (of the loop variables of the outer "for loop"s) with integer coefficients (and is always non-negative at every evaluation). {...} contains a non-empty sequence of "for loop" or "output statement".

Translated cyclers, cyclers, bouncers, "finned" and "helix" are examples of history-linear TMs.

Counters (non-unary), bells and fractal machines are not history-linear.

Examples

1RB1RA_0RC0LF_0RD0RF_1LE0RA_1LB---_1RC1LD (bbch)

1RB1RA_0RC1LB_1RD0RA_1LE0LF_0LA0LD_---0RE (bbch)

1RB1LF_1LC1LD_1RD1LA_---0RE_1RB1RA_1LA0LB (bbch)

1RB1LA_0LC0RF_---0LD_1LE0RC_1RF1LD_1RD0RA (bbch) (has unbounded amount of repeaters)

1RB1RF_1LC0LD_1RE1RD_---0LE_1RF0RF_1LB1RA (bbch)

1RB1RA_0RC---_1RD0LC_0RE0RD_1LF0RA_1LF1LC (bbch)

1RB0RD_1RC---_1LD1RF_1LF1LE_0RC0LD_1RA0LF (bbch)

1RB1RA_1LC0LF_0LD0LB_1RE---_0LA0RC_1LB0RD (bbch)