History linear - Revision history

Polygon: Added links to the mentioned zoology

2025-08-27T16:12:26Z

Added links to the mentioned zoology

← Older revision		Revision as of 16:12, 27 August 2025
Line 5:		Line 5:
	* 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".		* 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 ==

Int-y1: update tm links

2025-07-09T01:56:39Z

update tm links

← Older revision		Revision as of 01:56, 9 July 2025
Line 10:		Line 10:

	== Examples ==		== Examples ==
	~~[https://bbchallenge.org/~~1RB1RA_0RC0LF_0RD0RF_1LE0RA_1LB---_1RC1LD ~~1RB1RA_0RC0LF_0RD0RF_1LE0RA_1LB---_1RC1LD]~~		{{TM\|1RB1RA_0RC0LF_0RD0RF_1LE0RA_1LB---_1RC1LD}}

	~~[https://bbchallenge.org/~~1RB1RA_0RC1LB_1RD0RA_1LE0LF_0LA0LD_---0RE ~~1RB1RA_0RC1LB_1RD0RA_1LE0LF_0LA0LD_---0RE]~~		{{TM\|1RB1RA_0RC1LB_1RD0RA_1LE0LF_0LA0LD_---0RE}}

	~~[https://bbchallenge.org/~~1RB1LF_1LC1LD_1RD1LA_---0RE_1RB1RA_1LA0LB ~~1RB1LF_1LC1LD_1RD1LA_---0RE_1RB1RA_1LA0LB]~~		{{TM\|1RB1LF_1LC1LD_1RD1LA_---0RE_1RB1RA_1LA0LB}}

	~~[https://bbchallenge.org/~~1RB1LA_0LC0RF_---0LD_1LE0RC_1RF1LD_1RD0RA ~~1RB1LA_0LC0RF_---0LD_1LE0RC_1RF1LD_1RD0RA]~~ (has unbounded amount of repeaters)		{{TM\|1RB1LA_0LC0RF_---0LD_1LE0RC_1RF1LD_1RD0RA}} (has unbounded amount of repeaters)

	~~[https://bbchallenge.org/~~1RB1RF_1LC0LD_1RE1RD_---0LE_1RF0RF_1LB1RA ~~1RB1RF_1LC0LD_1RE1RD_---0LE_1RF0RF_1LB1RA]~~		{{TM\|1RB1RF_1LC0LD_1RE1RD_---0LE_1RF0RF_1LB1RA}}

	~~[https://bbchallenge.org/~~1RB1RA_0RC---_1RD0LC_0RE0RD_1LF0RA_1LF1LC ~~1RB1RA_0RC---_1RD0LC_0RE0RD_1LF0RA_1LF1LC]~~		{{TM\|1RB1RA_0RC---_1RD0LC_0RE0RD_1LF0RA_1LF1LC}}

	~~[https://bbchallenge.org/~~1RB0RD_1RC---_1LD1RF_1LF1LE_0RC0LD_1RA0LF ~~1RB0RD_1RC---_1LD1RF_1LF1LE_0RC0LD_1RA0LF]~~		{{TM\|1RB0RD_1RC---_1LD1RF_1LF1LE_0RC0LD_1RA0LF}}

	~~[https://bbchallenge.org/1RB1RA_1LC0LF_0LD0LB_1RE---_0LA0RC_1LB0RD~~ 1RB1RA_1LC0LF_0LD0LB_1RE---_0LA0RC_1LB0RD]		{{TM\|1RB1RA_1LC0LF_0LD0LB_1RE---_0LA0RC_1LB0RD}}

			[[Category: Zoology]]

Int-y1: grammar fixes

2024-07-24T02:55:02Z

grammar fixes

← Older revision		Revision as of 02:55, 24 July 2024
Line 1:		Line 1:
	~~== Definition ==~~		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 is history-linear, iff its transition history (a sequence of (state,read symbol)) can be generated by a program ~~consist~~ of "~~for loop~~" and "~~output statement~~".

	* 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 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".		* 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.

Mxdys: init, add definition and examples

2024-05-28T19:35:33Z

init, add definition and examples

New page

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

* 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 ==
[https://bbchallenge.org/1RB1RA_0RC0LF_0RD0RF_1LE0RA_1LB---_1RC1LD 1RB1RA_0RC0LF_0RD0RF_1LE0RA_1LB---_1RC1LD]

[https://bbchallenge.org/1RB1RA_0RC1LB_1RD0RA_1LE0LF_0LA0LD_---0RE 1RB1RA_0RC1LB_1RD0RA_1LE0LF_0LA0LD_---0RE]

[https://bbchallenge.org/1RB1LF_1LC1LD_1RD1LA_---0RE_1RB1RA_1LA0LB 1RB1LF_1LC1LD_1RD1LA_---0RE_1RB1RA_1LA0LB]

[https://bbchallenge.org/1RB1LA_0LC0RF_---0LD_1LE0RC_1RF1LD_1RD0RA 1RB1LA_0LC0RF_---0LD_1LE0RC_1RF1LD_1RD0RA] (has unbounded amount of repeaters)

[https://bbchallenge.org/1RB1RF_1LC0LD_1RE1RD_---0LE_1RF0RF_1LB1RA 1RB1RF_1LC0LD_1RE1RD_---0LE_1RF0RF_1LB1RA]

[https://bbchallenge.org/1RB1RA_0RC---_1RD0LC_0RE0RD_1LF0RA_1LF1LC 1RB1RA_0RC---_1RD0LC_0RE0RD_1LF0RA_1LF1LC]

[https://bbchallenge.org/1RB0RD_1RC---_1LD1RF_1LF1LE_0RC0LD_1RA0LF 1RB0RD_1RC---_1LD1RF_1LF1LE_0RC0LD_1RA0LF]

[https://bbchallenge.org/1RB1RA_1LC0LF_0LD0LB_1RE---_0LA0RC_1LB0RD 1RB1RA_1LC0LF_0LD0LB_1RE---_0LA0RC_1LB0RD]