History linear: Difference between revisions
Jump to navigation
Jump to search
(init, add definition and examples) |
(Added links to the mentioned zoology) |
||
| (2 intermediate revisions by one other user not shown) | |||
| 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 cycler|Translated cyclers]], [[Cycler|cyclers]], [[bouncers]], "finned" and "helix" are examples of history-linear TMs. | ||
Counters (non-unary), bells and fractal machines are not history-linear. | [[Counter|Counters]] (non-unary), [[bell|bells]] and [[fractal]] machines are not history-linear. | ||
== Examples == | == Examples == | ||
{{TM|1RB1RA_0RC0LF_0RD0RF_1LE0RA_1LB---_1RC1LD}} | |||
{{TM|1RB1RA_0RC1LB_1RD0RA_1LE0LF_0LA0LD_---0RE}} | |||
{{TM|1RB1LF_1LC1LD_1RD1LA_---0RE_1RB1RA_1LA0LB}} | |||
{{TM|1RB1LA_0LC0RF_---0LD_1LE0RC_1RF1LD_1RD0RA}} (has unbounded amount of repeaters) | |||
{{TM|1RB1RF_1LC0LD_1RE1RD_---0LE_1RF0RF_1LB1RA}} | |||
{{TM|1RB1RA_0RC---_1RD0LC_0RE0RD_1LF0RA_1LF1LC}} | |||
{{TM|1RB0RD_1RC---_1LD1RF_1LF1LE_0RC0LD_1RA0LF}} | |||
{{TM|1RB1RA_1LC0LF_0LD0LB_1RE---_0LA0RC_1LB0RD}} | |||
[[Category: Zoology]] | |||
Latest revision as of 16:12, 27 August 2025
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 (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)