History linear: Difference between revisions
Jump to navigation
Jump to search
(init, add definition and examples) |
(grammar fixes) |
||
| Line 1: | Line 1: | ||
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". | |||
We call a TM | |||
* Each "output statement" outputs a fixed transition of the TM. | * 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 | * A "for loop" is like <code>for(int i=0;i<n;++i){...}</code> or <code>for(int i=0;;++i)</code> 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). <code>{...}</code> contains a non-empty sequence of "for loop" or "output statement". | ||
Translated cyclers, cyclers, bouncers, "finned" and "helix" are examples of history-linear TMs. | Translated cyclers, cyclers, bouncers, "finned" and "helix" are examples of history-linear TMs. | ||
Revision as of 02:55, 24 July 2024
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){...}orfor(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
1RB1RA_0RC1LB_1RD0RA_1LE0LF_0LA0LD_---0RE
1RB1LF_1LC1LD_1RD1LA_---0RE_1RB1RA_1LA0LB
1RB1LA_0LC0RF_---0LD_1LE0RC_1RF1LD_1RD0RA (has unbounded amount of repeaters)
1RB1RF_1LC0LD_1RE1RD_---0LE_1RF0RF_1LB1RA
1RB1RA_0RC---_1RD0LC_0RE0RD_1LF0RA_1LF1LC