Translated cycler - Revision history

Sligocki: Link Shen Lin

2025-12-04T17:40:14Z

Link Shen Lin

← Older revision		Revision as of 17:40, 4 December 2025
Line 1:		Line 1:
	[[File:Translated_cycler_44394115_annotated.svg\|right\|thumb\|Example "Translated cycler": 45-step space-time diagram of bbchallenge's machine {{TM\|1RB0RE_0LC1RC_0RD1LA_1LE---_1LB1RC}}. The same bounded pattern is being translated to the right forever. The text annotations illustrate the main idea for recognising "Translated Cyclers": find two configurations that break a record (i.e. visit a memory cell that was never visited before) in the same state (here state D) such that the content of the memory tape at distance L from the record positions is the same in both record configurations. Distance L is defined as being the maximum distance to record position 1 that was visited between the configuration of record 1 and record 2.]]		[[File:Translated_cycler_44394115_annotated.svg\|right\|thumb\|Example "Translated cycler": 45-step space-time diagram of bbchallenge's machine {{TM\|1RB0RE_0LC1RC_0RD1LA_1LE---_1LB1RC}}. The same bounded pattern is being translated to the right forever. The text annotations illustrate the main idea for recognising "Translated Cyclers": find two configurations that break a record (i.e. visit a memory cell that was never visited before) in the same state (here state D) such that the content of the memory tape at distance L from the record positions is the same in both record configurations. Distance L is defined as being the maximum distance to record position 1 that was visited between the configuration of record 1 and record 2.]]

	A '''translated cycler''' (also known as a '''partial recurrent''' or '''Lin recurrent''' TM) is a non-halting [[Turing machine]] which eventually exhibits a traveling cyclic behavior. Specifically, a TM has ~~ented~~ a translated cycle once it begins repeating a fixed sequence of transition rules in such a way that it will continue repeating them forever. It is, by far, the most common type of non-halting behavior. For example, 95% of all infinite [[BB(6)]] TMs are translated cyclers (which have cycled at least once within the first 1000 steps) and this number is relatively consistent across other BB "domains" (Say BB(5), BB(3,3), etc.).		A '''translated cycler''' (also known as a '''partial recurrent''' or '''Lin recurrent''' TM) is a non-halting [[Turing machine]] which eventually exhibits a traveling cyclic behavior. Specifically, a TM has entered a translated cycle once it begins repeating a fixed sequence of transition rules in such a way that it will continue repeating them forever. It is, by far, the most common type of non-halting behavior. For example, 95% of all infinite [[BB(6)]] TMs are translated cyclers (which have cycled at least once within the first 1000 steps) and this number is relatively consistent across other BB "domains" (Say BB(5), BB(3,3), etc.).

	See [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 3] of bbchallenge's deciders write-up for a formal presentation of translated cyclers.		See [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 3] of bbchallenge's deciders write-up for a formal presentation of translated cyclers.

	== History ==		== History ==
	Translated cycling behavior was first described by Shen Lin in his proof of [[BB(3)]] where he called it "partial recurrence".<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2): 196–212. <nowiki>https://doi.org/10.1145/321264.321270</nowiki></ref> He describes an algorithm for detecting it which appears to be the first documented example of a [[decider]]. This behavior has been given many names over the years. For example, Nick Drozd calls this Lin recurrence in honor of Shen Lin.<ref>Nick Drozd. 2021. [https://nickdrozd.github.io/2021/02/24/lin-recurrence-and-lins-algorithm.html Lin Recurrence and Lin's Algorithm]</ref>		Translated cycling behavior was first described by [[Shen Lin]] in his proof of [[BB(3)]] where he called it "partial recurrence".<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2): 196–212. <nowiki>https://doi.org/10.1145/321264.321270</nowiki></ref> He describes an algorithm for detecting it which appears to be the first documented example of a [[decider]]. This behavior has been given many names over the years. For example, Nick Drozd calls this Lin recurrence in honor of Shen Lin.<ref>Nick Drozd. 2021. [https://nickdrozd.github.io/2021/02/24/lin-recurrence-and-lins-algorithm.html Lin Recurrence and Lin's Algorithm]</ref>

	== Record breaking ==		== Record breaking ==

MrSolis at 22:48, 7 October 2025

2025-10-07T22:48:28Z

← Older revision		Revision as of 22:48, 7 October 2025
Line 45:		Line 45:

	* [[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.		* [[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.
	* {{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a period of 1 step and a cycle offset of 1 symbol to the left. Its tape configuration in record <math>k</math> is <math>0^\infty\;\textrm{<}\textrm{C} 1^{k} 0^\infty\;</math>.		* {{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a period of 1 step and a cycle offset of 1 symbol to the left. Its tape configuration in record <math>k</math> is <math>0^\infty\;\textrm{<}\textrm{C}\;1^{k} 0^\infty\;</math>.

	== See also ==		== See also ==

MrSolis at 22:48, 7 October 2025

2025-10-07T22:48:12Z

← Older revision		Revision as of 22:48, 7 October 2025
Line 45:		Line 45:

	* [[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.		* [[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.
	* {{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a period of 1 step and a cycle offset of 1 symbol to the left. Its tape configuration in record <math>k</math> is <math>0^\infty\;\textrm{<C} 1^{k} 0^\infty\;</math>.		* {{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a period of 1 step and a cycle offset of 1 symbol to the left. Its tape configuration in record <math>k</math> is <math>0^\infty\;\textrm{<}\textrm{C} 1^{k} 0^\infty\;</math>.

	== See also ==		== See also ==

MrSolis: :O

2025-10-07T22:47:53Z

← Older revision		Revision as of 22:47, 7 October 2025
Line 23:		Line 23:
	A translated cycle can be seen as an infinite [[shift rule]]. For example, consider the TM {{TM\|1RB0RE_0LC1RC_0RD1LA_1LE---_1LB1RC\|non-halt}} in the image at the right. It performs the following [[transition rule]]:<math display="block">\begin{array}{l}		A translated cycle can be seen as an infinite [[shift rule]]. For example, consider the TM {{TM\|1RB0RE_0LC1RC_0RD1LA_1LE---_1LB1RC\|non-halt}} in the image at the right. It performs the following [[transition rule]]:<math display="block">\begin{array}{l}
	\\		\\
	10 \; \textrm{D>} \; 00 \xrightarrow{10} 00 \; 10 \; \textrm{D>} \\		10\;\textrm{D}\textrm{>}\;00\xrightarrow{10}00\;10\;\textrm{D}\textrm{>} \\
	\end{array}</math>		\end{array}</math>

	which can be repeated to form the shift rule:<math display="block">\begin{array}{l}		which can be repeated to form the shift rule:<math display="block">\begin{array}{l}
	\\		\\
	10 \; \textrm{D>} \; {00}^n \xrightarrow{10n} {00}^n \; 10 \; \textrm{D>} \\		10\;\textrm{D}\textrm{>}\;{00}^n\xrightarrow{10n}{00}^n\;10\;\textrm{D}\textrm{>} \\
	\end{array}</math>		\end{array}</math>

	Furthermore, on step 6, this TM is in config		Furthermore, on step 6, this TM is in config

	<math display="block">0^\infty \; 1 \; 10 \; \textrm{D>} \; 0^\infty</math>		<math display="block">0^\infty\;1\;10\;\textrm{D}\textrm{>}\;0^\infty</math>

	Therefore, we can see that for all <math>n \ge 0</math> we can apply the shift rule and so this TM can never halt.		Therefore, we can see that for all <math>n \ge 0</math> we can apply the shift rule and so this TM can never halt.

Polygon: /* Notable translated cyclers */ cycle time -> period

2025-08-28T11:50:52Z

Notable translated cyclers: cycle time -> period

← Older revision		Revision as of 11:50, 28 August 2025
Line 45:		Line 45:

	* [[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.		* [[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.
	* {{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a ~~cycle time~~ of 1 step and a cycle offset of 1 symbol to the left. Its tape configuration in record <math>k</math> is <math>0^\infty\;\textrm{<C} 1^{k} 0^\infty\;</math>.		* {{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a period of 1 step and a cycle offset of 1 symbol to the left. Its tape configuration in record <math>k</math> is <math>0^\infty\;\textrm{<C} 1^{k} 0^\infty\;</math>.

	== See also ==		== See also ==

Sligocki: /* Notable translated cyclers */ Make a bulleted list.

2025-08-27T20:21:33Z

Notable translated cyclers: Make a bulleted list.

← Older revision		Revision as of 20:21, 27 August 2025
Line 44:		Line 44:
	== Notable translated cyclers ==		== Notable translated cyclers ==

	[[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.		* [[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.
			* {{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a cycle time of 1 step and a cycle offset of 1 symbol to the left. Its tape configuration in record <math>k</math> is <math>0^\infty\;\textrm{<C} 1^{k} 0^\infty\;</math>.
	{{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a cycle time of 1 step and a cycle offset of 1 symbol to the left. Its tape configuration in record <math>k</math> is <math>0^\infty\;\textrm{<C} 1^{k} 0^\infty\;</math>.

	== See also ==		== See also ==

Polygon: /* Notable translated cyclers */ Added record tape configuration

2025-08-27T19:31:32Z

Notable translated cyclers: Added record tape configuration

← Older revision		Revision as of 19:31, 27 August 2025
Line 46:		Line 46:
	[[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.		[[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.

	{{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a cycle time of 1 step and a cycle offset of 1 symbol to the left.		{{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a cycle time of 1 step and a cycle offset of 1 symbol to the left. Its tape configuration in record <math>k</math> is <math>0^\infty\;\textrm{<C} 1^{k} 0^\infty\;</math>.

	== See also ==		== See also ==

Polygon: /* Notable translated cyclers */ Removed excess a

2025-08-27T19:02:17Z

Notable translated cyclers: Removed excess a

← Older revision		Revision as of 19:02, 27 August 2025
Line 46:		Line 46:
	[[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.		[[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.

	{{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is a the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a cycle time of 1 step and a cycle offset of 1 symbol to the left.		{{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a cycle time of 1 step and a cycle offset of 1 symbol to the left.

	== See also ==		== See also ==

Polygon: /* Notable translated cyclers */ Added current BBB(4,2) and BLB(4,2) champion

2025-08-27T19:01:33Z

Notable translated cyclers: Added current BBB(4,2) and BLB(4,2) champion

← Older revision		Revision as of 19:01, 27 August 2025
Line 45:		Line 45:

	[[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.		[[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of about <math>5.42 \times 10^{51}</math>.

			{{TM\|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} is a the current [[Beeping Busy Beaver]] (4,2) and [[Blanking Busy Beaver]] (4,2) champion. It has a preperiod of 32,779,478 steps, a cycle time of 1 step and a cycle offset of 1 symbol to the left.

	== See also ==		== See also ==

Polygon: Mentioned BBS and BBP

2025-08-17T11:00:28Z

Mentioned BBS and BBP

← Older revision		Revision as of 11:00, 17 August 2025
Line 16:		Line 16:
	* The '''cycle period''' is 10 steps. This is the number of steps from record 1 to record 2.		* The '''cycle period''' is 10 steps. This is the number of steps from record 1 to record 2.
	* The '''cycle offset''' is 2 symbols to the right. In other words, after each cycle, the TM moves 2 places to the right.		* The '''cycle offset''' is 2 symbols to the right. In other words, after each cycle, the TM moves 2 places to the right.
	* The '''cycle start time''' is 6 steps. This is the position of record 1.		* The '''cycle start time''' is 6 steps. This is the position of record 1. The cycle start time of a translated cycler can also be called its '''preperiod'''.

	Translated cyclers are close to [[Cycler\|Cyclers]] in the sense that they are only repeating a pattern but there is added complexity as they are able to translate the pattern in space at the same time, hence the decider for Cyclers cannot directly apply here.		Translated cyclers are close to [[Cycler\|Cyclers]] in the sense that they are only repeating a pattern but there is added complexity as they are able to translate the pattern in space at the same time, hence the decider for Cyclers cannot directly apply here.
Line 36:		Line 36:

	Therefore, we can see that for all <math>n \ge 0</math> we can apply the shift rule and so this TM can never halt.		Therefore, we can see that for all <math>n \ge 0</math> we can apply the shift rule and so this TM can never halt.

			==Related Functions==

			* Busy Preperiodic Beaver ([[BBS]](n,m)): The longest possible preperiod of a cycler or translated cycler with n states and m symbols.
			* Busy Periodic Beaver ([[BBP]](n,m)): The longest possible period of a cycler or translated cycler with n states and m symbols.

	== Notable translated cyclers ==		== Notable translated cyclers ==