Fractal - Revision history

Icy: /* Step counts */ Make it more obvious how the step count equations were obtained

2024-12-30T05:56:33Z

Step counts: Make it more obvious how the step count equations were obtained

← Older revision		Revision as of 05:56, 30 December 2024
Line 17:		Line 17:

	=== Step counts ===		=== Step counts ===
	~~The~~ step counts ''a<sub>n</sub>'' = \|'''R'''<sub>n</sub>\| obey the recurrence		By taking lengths of the formulas in the equations for '''R'''<sub>''n'', ''m''</sub>, we find that the step counts ''a<sub>n</sub>'' = \|'''R'''<sub>n</sub>\| obey the recurrence
	:<math>\begin{align}		:<math>\begin{align}
	a_{0,m} &= m + 3 \\		a_{0,m} &= m + 3 \\

Icy: Added step counts

2024-11-15T19:53:45Z

Added step counts

@@ Line 12: / Line 12: @@
 \mathbf R_{n+1,m} &= \mathbf R_{n,m}\ \mathrm D0^{2^n+m+1}\ \mathrm D1\ \mathrm A1^{2^{n+1}-1}\ \mathbf R_{n,0}\ \mathrm D1\ \mathbf R_{n,m + 2^n}.
 \end{align}</math>
-We can verify by induction on ''n'' that<blockquote>'''R'''<sub>''n'', ''m''</sub>: <code>A (0^2<sup>n</sup>)<0(1<sup>m</sup>)(0^(2<sup>n+1</sup>-1))  →  D (1^2<sup>n+1</sup>)(0^(2<sup>n</sup>+m))></code>.</blockquote>The source of '''R'''<sub>''n'', 0</sub> matches the starting configuration, and the length of '''R'''<sub>''n'', 0</sub> is easily seen to grow without bound. It follows that the [[transcript]] of this Turing machine is the limit of '''R'''<sub>''n'', 0</sub> as ''n'' approaches ∞.
+We can verify by induction on ''n'' that
 [[Category: Zoology]]

Icy at 18:46, 15 November 2024

2024-11-15T18:46:25Z

← Older revision		Revision as of 18:46, 15 November 2024
Line 12:		Line 12:
	\mathbf R_{n+1,m} &= \mathbf R_{n,m}\ \mathrm D0^{2^n+m+1}\ \mathrm D1\ \mathrm A1^{2^{n+1}-1}\ \mathbf R_{n,0}\ \mathrm D1\ \mathbf R_{n,m + 2^n}.		\mathbf R_{n+1,m} &= \mathbf R_{n,m}\ \mathrm D0^{2^n+m+1}\ \mathrm D1\ \mathrm A1^{2^{n+1}-1}\ \mathbf R_{n,0}\ \mathrm D1\ \mathbf R_{n,m + 2^n}.
	\end{align}</math>		\end{align}</math>
	We can verify by induction on ''n'' that<blockquote>'''R'''<sub>''n'', ''m''</sub>: <code>A (0^2<sup>n</sup>)<0(1<sup>m</sup>)(0^(2<sup>n+1</sup>-1)) → D (1^2<sup>n+1</sup>)(0^(2<sup>n</sup>+m))></code>.</blockquote>The source of '''R'''<sub>''n'', 0</sub> matches the starting configuration, and the length of '''R'''<sub>''n'', 0</sub> is easily seen to grow without bound. It follows that the [[transcript]] of this Turing machine is the limit of '''R'''<sub>''n'', 0</sub> as n approaches ∞.		We can verify by induction on ''n'' that<blockquote>'''R'''<sub>''n'', ''m''</sub>: <code>A (0^2<sup>n</sup>)<0(1<sup>m</sup>)(0^(2<sup>n+1</sup>-1)) → D (1^2<sup>n+1</sup>)(0^(2<sup>n</sup>+m))></code>.</blockquote>The source of '''R'''<sub>''n'', 0</sub> matches the starting configuration, and the length of '''R'''<sub>''n'', 0</sub> is easily seen to grow without bound. It follows that the [[transcript]] of this Turing machine is the limit of '''R'''<sub>''n'', 0</sub> as ''n'' approaches ∞.

	[[Category: Zoology]]		[[Category: Zoology]]

Icy: Typo: A should be D on RHS

2024-11-15T18:46:01Z

Typo: A should be D on RHS

← Older revision		Revision as of 18:46, 15 November 2024
Line 12:		Line 12:
	\mathbf R_{n+1,m} &= \mathbf R_{n,m}\ \mathrm D0^{2^n+m+1}\ \mathrm D1\ \mathrm A1^{2^{n+1}-1}\ \mathbf R_{n,0}\ \mathrm D1\ \mathbf R_{n,m + 2^n}.		\mathbf R_{n+1,m} &= \mathbf R_{n,m}\ \mathrm D0^{2^n+m+1}\ \mathrm D1\ \mathrm A1^{2^{n+1}-1}\ \mathbf R_{n,0}\ \mathrm D1\ \mathbf R_{n,m + 2^n}.
	\end{align}</math>		\end{align}</math>
	We can verify by induction on ''n'' that<blockquote>'''R'''<sub>''n'', ''m''</sub>: <code>A (0^2<sup>n</sup>)<0(1<sup>m</sup>)(0^(2<sup>n+1</sup>-1)) → A (1^2<sup>n+1</sup>)(0^(2<sup>n</sup>+m))></code>.</blockquote>The source of '''R'''<sub>''n'', 0</sub> matches the starting configuration, and the length of '''R'''<sub>''n'', 0</sub> is easily seen to grow without bound. It follows that the [[transcript]] of this Turing machine is the limit of '''R'''<sub>''n'', 0</sub> as n approaches ∞.		We can verify by induction on ''n'' that<blockquote>'''R'''<sub>''n'', ''m''</sub>: <code>A (0^2<sup>n</sup>)<0(1<sup>m</sup>)(0^(2<sup>n+1</sup>-1)) → D (1^2<sup>n+1</sup>)(0^(2<sup>n</sup>+m))></code>.</blockquote>The source of '''R'''<sub>''n'', 0</sub> matches the starting configuration, and the length of '''R'''<sub>''n'', 0</sub> is easily seen to grow without bound. It follows that the [[transcript]] of this Turing machine is the limit of '''R'''<sub>''n'', 0</sub> as n approaches ∞.

	[[Category: Zoology]]		[[Category: Zoology]]

Icy: Added category

2024-11-15T18:35:19Z

Added category

← Older revision		Revision as of 18:35, 15 November 2024
Line 13:		Line 13:
	\end{align}</math>		\end{align}</math>
	We can verify by induction on ''n'' that<blockquote>'''R'''<sub>''n'', ''m''</sub>: <code>A (0^2<sup>n</sup>)<0(1<sup>m</sup>)(0^(2<sup>n+1</sup>-1)) → A (1^2<sup>n+1</sup>)(0^(2<sup>n</sup>+m))></code>.</blockquote>The source of '''R'''<sub>''n'', 0</sub> matches the starting configuration, and the length of '''R'''<sub>''n'', 0</sub> is easily seen to grow without bound. It follows that the [[transcript]] of this Turing machine is the limit of '''R'''<sub>''n'', 0</sub> as n approaches ∞.		We can verify by induction on ''n'' that<blockquote>'''R'''<sub>''n'', ''m''</sub>: <code>A (0^2<sup>n</sup>)<0(1<sup>m</sup>)(0^(2<sup>n+1</sup>-1)) → A (1^2<sup>n+1</sup>)(0^(2<sup>n</sup>+m))></code>.</blockquote>The source of '''R'''<sub>''n'', 0</sub> matches the starting configuration, and the length of '''R'''<sub>''n'', 0</sub> is easily seen to grow without bound. It follows that the [[transcript]] of this Turing machine is the limit of '''R'''<sub>''n'', 0</sub> as n approaches ∞.

			[[Category: Zoology]]

Icy at 18:24, 15 November 2024

2024-11-15T18:24:11Z

← Older revision		Revision as of 18:24, 15 November 2024
Line 3:		Line 3:

	== Example ==		== Example ==
	The fractal {{TM\|1RB0LA_1RC---_0RD0RC_1LD0LA}} is shown on the right, and portrays the most common type of fractal Turing machine. ~~One can hypothesize that the~~ fractal consists of two major parts: the left part consists of copies of the fractal at smaller scales, while the right part consists of an interrupted [[bouncer]].		The fractal {{TM\|1RB0LA_1RC---_0RD0RC_1LD0LA}} is shown on the right, and portrays the most common type of fractal Turing machine. The fractal consists of two major parts: the left part consists of copies of the fractal at smaller scales, while the right part consists of an interrupted [[bouncer]].

	The idea for the following analysis is to notice that, if '''X''' denotes the top quarter of the image, the spacetime diagram for the fractal seems to consist of two copies of '''X''', followed by another copy of '''X''' but modified such that the bouncers on the right are all increased in size by some constant. Hence we must consider not only '''X''', but also variants of '''X''' corresponding to any starting bouncer size. In other words, the starting bouncer size must be an additional parameter to our recursion. There will also be fillers between the copies of '''X''' in order to move the head to desired positions.		The idea for the following analysis is to notice that, if '''X''' denotes the top quarter of the image, the spacetime diagram for the fractal seems to consist of two copies of '''X''', followed by another copy of '''X''' but modified such that the bouncers on the right are all increased in size by some constant. Hence we must consider not only '''X''', but also variants of '''X''' corresponding to any starting bouncer size. In other words, the starting bouncer size must be an additional parameter to our recursion. There will also be fillers between the copies of '''X''' in order to move the head to desired positions.

Icy at 17:51, 15 November 2024

2024-11-15T17:51:14Z

← Older revision		Revision as of 17:51, 15 November 2024
Line 5:		Line 5:
	The fractal {{TM\|1RB0LA_1RC---_0RD0RC_1LD0LA}} is shown on the right, and portrays the most common type of fractal Turing machine. One can hypothesize that the fractal consists of two major parts: the left part consists of copies of the fractal at smaller scales, while the right part consists of an interrupted [[bouncer]].		The fractal {{TM\|1RB0LA_1RC---_0RD0RC_1LD0LA}} is shown on the right, and portrays the most common type of fractal Turing machine. One can hypothesize that the fractal consists of two major parts: the left part consists of copies of the fractal at smaller scales, while the right part consists of an interrupted [[bouncer]].

	The idea for the following analysis is to notice that, if '''X''' denotes the top quarter of the image, the spacetime diagram for the fractal seems to consist of two copies of '''X''', followed by another copy of '''X''' but modified such that the bouncers on the right are all increased in size by some constant. Hence we must consider only '''X''' but variants of '''X''' corresponding to any starting bouncer size. In other words, the starting bouncer size must be an additional parameter to our recursion. There will also be fillers between the copies of '''X''' in order to move the head to desired positions.		The idea for the following analysis is to notice that, if '''X''' denotes the top quarter of the image, the spacetime diagram for the fractal seems to consist of two copies of '''X''', followed by another copy of '''X''' but modified such that the bouncers on the right are all increased in size by some constant. Hence we must consider not only '''X''', but also variants of '''X''' corresponding to any starting bouncer size. In other words, the starting bouncer size must be an additional parameter to our recursion. There will also be fillers between the copies of '''X''' in order to move the head to desired positions.

	With this idea, define a two-parameter family of macro steps '''R'''<sub>''n'', ''m''</sub> recursively as follows:		With this idea, define a two-parameter family of macro steps '''R'''<sub>''n'', ''m''</sub> recursively as follows:

Icy at 17:48, 15 November 2024

2024-11-15T17:48:35Z

← Older revision		Revision as of 17:48, 15 November 2024
Line 12:		Line 12:
	\mathbf R_{n+1,m} &= \mathbf R_{n,m}\ \mathrm D0^{2^n+m+1}\ \mathrm D1\ \mathrm A1^{2^{n+1}-1}\ \mathbf R_{n,0}\ \mathrm D1\ \mathbf R_{n,m + 2^n}.		\mathbf R_{n+1,m} &= \mathbf R_{n,m}\ \mathrm D0^{2^n+m+1}\ \mathrm D1\ \mathrm A1^{2^{n+1}-1}\ \mathbf R_{n,0}\ \mathrm D1\ \mathbf R_{n,m + 2^n}.
	\end{align}</math>		\end{align}</math>
	We can verify by induction on ''n'' that<blockquote>'''R'''<sub>''n'', ''m''</sub>: <code>A (0^2<sup>n</sup>)<0(1<sup>m</sup>)(0^(2<sup>n+1</sup>-1)) → (1^2<sup>n+1</sup>)(0^(2<sup>n</sup>+m))></code>.</blockquote>The source of '''R'''<sub>''n'', 0</sub> matches the starting configuration, and the length of '''R'''<sub>''n'', 0</sub> is easily seen to grow without bound. It follows that the [[transcript]] of this Turing machine is the limit of '''R'''<sub>''n''</sub> as n approaches ∞.		We can verify by induction on ''n'' that<blockquote>'''R'''<sub>''n'', ''m''</sub>: <code>A (0^2<sup>n</sup>)<0(1<sup>m</sup>)(0^(2<sup>n+1</sup>-1)) → A (1^2<sup>n+1</sup>)(0^(2<sup>n</sup>+m))></code>.</blockquote>The source of '''R'''<sub>''n'', 0</sub> matches the starting configuration, and the length of '''R'''<sub>''n'', 0</sub> is easily seen to grow without bound. It follows that the [[transcript]] of this Turing machine is the limit of '''R'''<sub>''n'', 0</sub> as n approaches ∞.

Icy: Added fractal page

2024-11-15T17:46:48Z

Added fractal page

New page

[[File:1RB0LA 1RC--- 0RD0RC 1LD0LA.png|alt=1RB0LA_1RC---_0RD0RC_1LD0LA|thumb|The fractal {{TM|1RB0LA_1RC---_0RD0RC_1LD0LA}}.]]
A '''fractal''' is a [[non-halting Turing machine]] that displays self-similarity at different scales.

== Example ==
The fractal {{TM|1RB0LA_1RC---_0RD0RC_1LD0LA}} is shown on the right, and portrays the most common type of fractal Turing machine. One can hypothesize that the fractal consists of two major parts: the left part consists of copies of the fractal at smaller scales, while the right part consists of an interrupted [[bouncer]].

The idea for the following analysis is to notice that, if '''X''' denotes the top quarter of the image, the spacetime diagram for the fractal seems to consist of two copies of '''X''', followed by another copy of '''X''' but modified such that the bouncers on the right are all increased in size by some constant. Hence we must consider only '''X''' but variants of '''X''' corresponding to any starting bouncer size. In other words, the starting bouncer size must be an additional parameter to our recursion. There will also be fillers between the copies of '''X''' in order to move the head to desired positions.

With this idea, define a two-parameter family of macro steps '''R'''''n'', ''m'' recursively as follows:
:<math>\begin{align}
\mathbf R_{0,m} &= \mathrm A0\ \mathrm B0\ \mathrm C1^m\ \mathrm C0, \\
\mathbf R_{n+1,m} &= \mathbf R_{n,m}\ \mathrm D0^{2^n+m+1}\ \mathrm D1\ \mathrm A1^{2^{n+1}-1}\ \mathbf R_{n,0}\ \mathrm D1\ \mathbf R_{n,m + 2^n}.
\end{align}</math>
We can verify by induction on ''n'' that<blockquote>'''R'''''n'', ''m'': <code>A (0^2n)<0(1m)(0^(2n+1-1)) → (1^2n+1)(0^(2n+m))></code>.</blockquote>The source of '''R'''''n'', 0 matches the starting configuration, and the length of '''R'''''n'', 0 is easily seen to grow without bound. It follows that the [[transcript]] of this Turing machine is the limit of '''R'''''n'' as n approaches ∞.