Shift rule - Revision history

MrSolis: ╎|

2025-10-07T23:07:34Z

╎|

← Older revision		Revision as of 23:07, 7 October 2025
Line 3:		Line 3:
	A simple canonical example is that if we have a [[Turing machine]] with the transition <math>(\textrm{S}, 1) \to (0, R, \textrm{S})</math> then using [[directed head notation]]:		A simple canonical example is that if we have a [[Turing machine]] with the transition <math>(\textrm{S}, 1) \to (0, R, \textrm{S})</math> then using [[directed head notation]]:
	<math display="block">		<math display="block">
	\vphantom{\int}\textrm{S>} \; 1^n \xrightarrow{n} 0^n \; \textrm{S>}		\vphantom{\int}\textrm{S}\textrm{>}\;1^n \xrightarrow{n} 0^n\;\textrm{S}\textrm{>}
	</math>		</math>
	In other words, if the machine is in state <math>\textrm{S}</math> and the head is reading the leftmost of a sequence of <math>n</math> ones, then <math>n</math> steps later it will have moved to the right of this entire sequence of ones, converting them all to zeros.		In other words, if the machine is in state <math>\textrm{S}</math> and the head is reading the leftmost of a sequence of <math>n</math> ones, then <math>n</math> steps later it will have moved to the right of this entire sequence of ones, converting them all to zeros.

	To give a precise definition, suppose that there are words <math>t</math>, <math>r</math> and <math>r'</math> in the alphabet of the Turing machine in question,		To give a precise definition, suppose that there are words <math>t</math>, <math>r</math> and <math>r'</math> in the alphabet of the Turing machine in question,
	and assume that for some state <math>\textrm{S}</math> the machine transitions from <math>t \; \textrm{S>} \; r</math> to <math>r' t \; \textrm{S>}</math>. Then we have a ''right'' shift rule		and assume that for some state <math>\textrm{S}</math> the machine transitions from <math>t \; \textrm{S}\textrm{>} \; r</math> to <math>r' t \; \textrm{S}\textrm{>}</math>. Then we have a ''right'' shift rule
	<math display="block">		<math display="block">
	\displaystyle\vphantom{\int} t \; \textrm{S>} \; r \to r'\;t\;\textrm{S>}.		\displaystyle\vphantom{\int} t \; \textrm{S}\textrm{>} \; r \to r'\;t\;\textrm{S}\textrm{>}.
	</math>		</math>
	Similarly, if the machine transitions from <math> r \; \textrm{<S} \; t</math> to <math>\textrm{<S} \; t r'</math>, then we have a ''left'' shift rule		Similarly, if the machine transitions from <math> r \; \textrm{<}\textrm{S} \; t</math> to <math>\textrm{<}\textrm{S} \; t r'</math>, then we have a ''left'' shift rule
	<math display="block">		<math display="block">
	\vphantom{\int} r \; \textrm{<S} \; t \to \textrm{<S} \; t\;r'.		\vphantom{\int}r\;\textrm{<}\textrm{S}\;t\to\textrm{<}\textrm{S}\;t\;r'.
	</math>		</math>

Line 21:		Line 21:
	<math display="block">		<math display="block">
	\begin{array}{rcl}		\begin{array}{rcl}
	\displaystyle\vphantom{\int} 011 \; \textrm{<C} & \xrightarrow{3} & \textrm{<C} \; 101 \\		\displaystyle\vphantom{\int} 011 \; \textrm{<}\textrm{C} & \xrightarrow{3} & \textrm{<}\textrm{C} \; 101 \\
	\textrm{A>} \; 110 110 & \xrightarrow{10} & 011 011 \;\textrm{A>}		\textrm{A}\textrm{>} \; 110 110 & \xrightarrow{10} & 011 011 \;\textrm{A}\textrm{>}
	\end{array}		\end{array}
	</math>		</math>
Line 28:		Line 28:
	<math display="block">		<math display="block">
	\begin{array}{rcl}		\begin{array}{rcl}
	\displaystyle\vphantom{\int}011^n \; \textrm{<C} & \xrightarrow{3n} & \textrm{<C} \; 101^n \\		\displaystyle\vphantom{\int}011^n \; \textrm{<}\textrm{C} & \xrightarrow{3n} & \textrm{<}\textrm{C} \; 101^n \\
	\textrm{A>} \; {110 110}^n & \xrightarrow{10n} & {011 011}^n \;\textrm{A>} \\		\textrm{A}\textrm{>} \; {110 110}^n & \xrightarrow{10n} & {011 011}^n \;\textrm{A}\textrm{>} \\
	\end{array}		\end{array}
	</math>		</math>
	Shift rules can also depend upon additional "local context". For example, Skelet #1 also exhibits this transition:		Shift rules can also depend upon additional "local context". For example, Skelet #1 also exhibits this transition:
	<math display="block">		<math display="block">
	\vphantom{\int} 01 \; \textrm{<C} \; 1 \xrightarrow{6} \textrm{<C} \; 1 \; 01		\vphantom{\int} 01 \; \textrm{<}\textrm{C} \; 1 \xrightarrow{6} \textrm{<}\textrm{C} \; 1 \; 01
	</math>		</math>
	and since the resulting config has the same "context" (a 1 to the right of the head), this can be repeated as well to produce the shift rule:		and since the resulting config has the same "context" (a 1 to the right of the head), this can be repeated as well to produce the shift rule:
	<math display="block">		<math display="block">
	\vphantom{\int} 01^n \; \textrm{<C} \; 1 \xrightarrow{6n} \textrm{<C} \; 1 \; 01^n.		\vphantom{\int} 01^n \; \textrm{<}\textrm{C} \; 1 \xrightarrow{6n} \textrm{<}\textrm{C} \; 1 \; 01^n.
	</math>		</math>

Line 47:		Line 47:
	One of the main uses of shift rules is to [[Accelerated Simulator\|accelerate the simulation]] of Turing machines. For example, consider the simple [[bouncer]] {{TM\|1RB1LA_1LA1RB}} using the shift rules:		One of the main uses of shift rules is to [[Accelerated Simulator\|accelerate the simulation]] of Turing machines. For example, consider the simple [[bouncer]] {{TM\|1RB1LA_1LA1RB}} using the shift rules:
	<math display="block">\begin{array}{rcl}		<math display="block">\begin{array}{rcl}
	\displaystyle\vphantom{\int}1^n \; \textrm{<A} & \xrightarrow{n} & \textrm{<A} \; 1^n \\		\displaystyle\vphantom{\int}1^n \; \textrm{<}\textrm{A} & \xrightarrow{n} & \textrm{<}\textrm{A} \; 1^n \\
	\textrm{B>} \; 1^n & \xrightarrow{n} & 1^n \; \textrm{B>} \\		\textrm{B}\textrm{>} \; 1^n & \xrightarrow{n} & 1^n \; \textrm{B}\textrm{>} \\
	\end{array}</math>		\end{array}</math>

Line 54:		Line 54:

	<math display="block">\begin{array}{ll}		<math display="block">\begin{array}{ll}
	\text{Start}{:}&0^\infty \; \textrm{<A} \; 0^\infty \\		\text{Start}{:}&0^\infty \; \textrm{<}\textrm{A} \; 0^\infty \\
	\text{Step 1}{:}&0^\infty \; 1 \; \textrm{B>} \; 0^\infty \\		\text{Step 1}{:}&0^\infty \; 1 \; \textrm{B}\textrm{>} \; 0^\infty \\
	\text{Step 2}{:}&0^\infty \; 1 \; \textrm{<A} \; 1 \; 0^\infty \\		\text{Step 2}{:}&0^\infty \; 1 \; \textrm{<}\textrm{A} \; 1 \; 0^\infty \\
	\text{Step 3}{:}&0^\infty \; \textrm{<A} \; 1^2 \; 0^\infty \\		\text{Step 3}{:}&0^\infty \; \textrm{<}\textrm{A} \; 1^2 \; 0^\infty \\
	\qquad\qquad\qquad\vdots \\		\qquad\qquad\qquad\vdots \\
	\text{Step }2n^2+n{:}&0^\infty \; \textrm{<A} \; 1^{2n} \; 0^\infty \\		\text{Step }2n^2+n{:}&0^\infty \; \textrm{<}\textrm{A} \; 1^{2n} \; 0^\infty \\
	\text{Step }2n^2+n+1{:}&0^\infty \; 1 \; \textrm{B>} \; 1^{2n} \; 0^\infty \\		\text{Step }2n^2+n+1{:}&0^\infty \; 1 \; \textrm{B}\textrm{>} \; 1^{2n} \; 0^\infty \\
	\text{Step }2n^2+3n+1{:}&0^\infty \; 1^{2n+1} \; \textrm{B>} \; 0^\infty \\		\text{Step }2n^2+3n+1{:}&0^\infty \; 1^{2n+1} \; \textrm{B}\textrm{>} \; 0^\infty \\
	\text{Step }2n^2+3n+2{:}&0^\infty \; 1^{2n+1} \; \textrm{<A} \; 1 \; 0^\infty \\		\text{Step }2n^2+3n+2{:}&0^\infty \; 1^{2n+1} \; \textrm{<}\textrm{A} \; 1 \; 0^\infty \\
	\text{Step }2n^2+5n+3{:}&0^\infty \; \textrm{<A} \; 1^{2n+2} \; 0^\infty \\		\text{Step }2n^2+5n+3{:}&0^\infty \; \textrm{<}\textrm{A} \; 1^{2n+2} \; 0^\infty \\
	\qquad\qquad\qquad\vdots \\		\qquad\qquad\qquad\vdots \\
	\end{array}</math>		\end{array}</math>
Line 71:		Line 71:
	Any Turing machine that has at least one of the two following types of shift rules:		Any Turing machine that has at least one of the two following types of shift rules:
	<math display="block">		<math display="block">
	\displaystyle\vphantom{\int}t\;\textrm{S>} \; 0^n \to r'\;t\;\textrm{S>}\qquad\text{or}\qquad \displaystyle\vphantom{\int}0^n\;\textrm{<S}\;t\to \textrm{<S}\;t\;r',		\displaystyle\vphantom{\int}t\;\textrm{S}\textrm{>} \; 0^n \to r'\;t\;\textrm{S}\textrm{>}\qquad\text{or}\qquad \displaystyle\vphantom{\int}0^n\;\textrm{<}\textrm{S}\;t\to \textrm{<}\textrm{S}\;t\;r',
	</math>		</math>
	and which eventually reaches the configuration <math>t\;\textrm{S>}\;0^\infty</math> (for the first rule) or <math>0^\infty\;\textrm{<S}\;t</math> (for the second rule) is non-halting, becoming a [[translated cycler]].		and which eventually reaches the configuration <math>t\;\textrm{S}\textrm{>}\;0^\infty</math> (for the first rule) or <math>0^\infty\;\textrm{<}\textrm{S}\;t</math> (for the second rule) is non-halting, becoming a [[translated cycler]].

	[[Category:Analysis Techniques]]		[[Category:Analysis Techniques]]

Int-y1: add category

2025-08-28T09:03:54Z

add category

← Older revision		Revision as of 09:03, 28 August 2025
Line 74:		Line 74:
	</math>		</math>
	and which eventually reaches the configuration <math>t\;\textrm{S>}\;0^\infty</math> (for the first rule) or <math>0^\infty\;\textrm{<S}\;t</math> (for the second rule) is non-halting, becoming a [[translated cycler]].		and which eventually reaches the configuration <math>t\;\textrm{S>}\;0^\infty</math> (for the first rule) or <math>0^\infty\;\textrm{<S}\;t</math> (for the second rule) is non-halting, becoming a [[translated cycler]].

			[[Category:Analysis Techniques]]

MrSolis at 23:54, 12 April 2025

2025-04-12T23:54:51Z

← Older revision		Revision as of 23:54, 12 April 2025
Line 59:		Line 59:
	\text{Step 3}{:}&0^\infty \; \textrm{<A} \; 1^2 \; 0^\infty \\		\text{Step 3}{:}&0^\infty \; \textrm{<A} \; 1^2 \; 0^\infty \\
	\qquad\qquad\qquad\vdots \\		\qquad\qquad\qquad\vdots \\
	&0^\infty \; \textrm{<A} \; 1^{2n} \; 0^\infty \\		\text{Step }2n^2+n{:}&0^\infty \; \textrm{<A} \; 1^{2n} \; 0^\infty \\
	&0^\infty \; 1 \; \textrm{B>} \; 1^{2n} \; 0^\infty \\		\text{Step }2n^2+n+1{:}&0^\infty \; 1 \; \textrm{B>} \; 1^{2n} \; 0^\infty \\
	&0^\infty \; 1^{2n+1} \; \textrm{B>} \; 0^\infty \\		\text{Step }2n^2+3n+1{:}&0^\infty \; 1^{2n+1} \; \textrm{B>} \; 0^\infty \\
	&0^\infty \; 1^{2n+1} \; \textrm{<A} \; 1 \; 0^\infty \\		\text{Step }2n^2+3n+2{:}&0^\infty \; 1^{2n+1} \; \textrm{<A} \; 1 \; 0^\infty \\
	&0^\infty \; \textrm{<A} \; 1^{2n+2} \; 0^\infty \\		\text{Step }2n^2+5n+3{:}&0^\infty \; \textrm{<A} \; 1^{2n+2} \; 0^\infty \\
	\qquad\qquad\qquad\vdots \\		\qquad\qquad\qquad\vdots \\
	\end{array}</math>		\end{array}</math>

MrSolis at 23:32, 12 April 2025

2025-04-12T23:32:33Z

← Older revision		Revision as of 23:32, 12 April 2025
Line 59:		Line 59:
	\text{Step 3}{:}&0^\infty \; \textrm{<A} \; 1^2 \; 0^\infty \\		\text{Step 3}{:}&0^\infty \; \textrm{<A} \; 1^2 \; 0^\infty \\
	\qquad\qquad\qquad\vdots \\		\qquad\qquad\qquad\vdots \\
	~~\text{Step }3n{:}~~&0^\infty \; \textrm{<A} \; 1^{2n} \; 0^\infty \\		&0^\infty \; \textrm{<A} \; 1^{2n} \; 0^\infty \\
	~~\text{Step }3n+1{:}~~&0^\infty \; 1 \; \textrm{B>} \; 1^{2n} \; 0^\infty \\		&0^\infty \; 1 \; \textrm{B>} \; 1^{2n} \; 0^\infty \\
	~~\text{Step }5n+1{:}~~&0^\infty \; 1^{2n+1} \; \textrm{B>} \; 0^\infty \\		&0^\infty \; 1^{2n+1} \; \textrm{B>} \; 0^\infty \\
	~~\text{Step }5n+2{:}~~&0^\infty \; 1^{2n+1} \; \textrm{<A} \; 1 \; 0^\infty \\		&0^\infty \; 1^{2n+1} \; \textrm{<A} \; 1 \; 0^\infty \\
	~~\text{Step }7n+3{:}~~&0^\infty \; \textrm{<A} \; 1^{2n+2} \; 0^\infty \\		&0^\infty \; \textrm{<A} \; 1^{2n+2} \; 0^\infty \\
	\qquad\qquad\qquad\vdots \\		\qquad\qquad\qquad\vdots \\
	\end{array}</math>		\end{array}</math>

MrSolis at 23:27, 12 April 2025

2025-04-12T23:27:54Z

← Older revision		Revision as of 23:27, 12 April 2025
Line 61:		Line 61:
	\text{Step }3n{:}&0^\infty \; \textrm{<A} \; 1^{2n} \; 0^\infty \\		\text{Step }3n{:}&0^\infty \; \textrm{<A} \; 1^{2n} \; 0^\infty \\
	\text{Step }3n+1{:}&0^\infty \; 1 \; \textrm{B>} \; 1^{2n} \; 0^\infty \\		\text{Step }3n+1{:}&0^\infty \; 1 \; \textrm{B>} \; 1^{2n} \; 0^\infty \\
	\text{Step }4n+1{:}&0^\infty \; 1^{2n+1} \; \textrm{B>} \; 0^\infty \\		\text{Step }5n+1{:}&0^\infty \; 1^{2n+1} \; \textrm{B>} \; 0^\infty \\
	\text{Step }4n+2{:}&0^\infty \; 1^{2n+1} \; \textrm{<A} \; 1 \; 0^\infty \\		\text{Step }5n+2{:}&0^\infty \; 1^{2n+1} \; \textrm{<A} \; 1 \; 0^\infty \\
	\text{Step }5n+3{:}&0^\infty \; \textrm{<A} \; 1^{2n+2} \; 0^\infty \\		\text{Step }7n+3{:}&0^\infty \; \textrm{<A} \; 1^{2n+2} \; 0^\infty \\
	\qquad\qquad\qquad\vdots \\		\qquad\qquad\qquad\vdots \\
	\end{array}</math>		\end{array}</math>

MrSolis: Visual Updates

2025-04-12T23:26:36Z

Visual Updates

← Older revision		Revision as of 23:26, 12 April 2025
Line 1:		Line 1:
	A '''shift rule''' (also called a '''chain rule''') is a finite sequence of transitions which may be repeated an arbitrary number of times to "jump" over an entire repeated block of symbols on a compressed tape.		A '''shift rule''' (also called a '''chain rule''') is a finite sequence of transitions which may be repeated an arbitrary number of times to "jump" over an entire repeated block of symbols on a compressed tape.

	A simple canonical example is that if we have a TM with transition <math>(S, 1) \to (0, R, S)</math> then using [[directed head notation]]:		A simple canonical example is that if we have a [[Turing machine]] with the transition <math>(\textrm{S}, 1) \to (0, R, \textrm{S})</math> then using [[directed head notation]]:
	<math display="block">		<math display="block">
	\vphantom{\int}\textrm{S>} \; 1^n \xrightarrow{n} 0^n \; \textrm{S>}		\vphantom{\int}\textrm{S>} \; 1^n \xrightarrow{n} 0^n \; \textrm{S>}
	</math>		</math>
	In other words, if the TM is in state S reading the leftmost of a sequence of n ones, then n steps later it will have moved to the right of this entire sequence of ones, converting them all to zeros.		In other words, if the machine is in state <math>\textrm{S}</math> and the head is reading the leftmost of a sequence of <math>n</math> ones, then <math>n</math> steps later it will have moved to the right of this entire sequence of ones, converting them all to zeros.

	To give a precise definition, suppose that there are words <math>t</math>, <math>r</math> and <math>r'</math> in the alphabet of the Turing machine in question,		To give a precise definition, suppose that there are words <math>t</math>, <math>r</math> and <math>r'</math> in the alphabet of the Turing machine in question,
	and assume that for some state S the machine transitions from <math>t \; \textrm{S>} \; r</math> to <math>r' t \; \textrm{S>}</math>. Then we have a ''right'' shift rule		and assume that for some state <math>\textrm{S}</math> the machine transitions from <math>t \; \textrm{S>} \; r</math> to <math>r' t \; \textrm{S>}</math>. Then we have a ''right'' shift rule
	<math display="block">		<math display="block">
	\vphantom{\int} t \; \textrm{S>} \; r \to r' t \; \textrm{S>}.		\displaystyle\vphantom{\int} t \; \textrm{S>} \; r \to r'\;t\;\textrm{S>}.
	</math>		</math>
	Similarly, if the machine transitions from <math> r \; \textrm{<S} \; t</math> to <math>\textrm{<S} \; t r'</math>, then we have a ''left'' shift rule		Similarly, if the machine transitions from <math> r \; \textrm{<S} \; t</math> to <math>\textrm{<S} \; t r'</math>, then we have a ''left'' shift rule
	<math display="block">		<math display="block">
	\vphantom{\int} r \; \textrm{<S} \; t \to \textrm{<S} \; t r'.		\vphantom{\int} r \; \textrm{<S} \; t \to \textrm{<S} \; t\;r'.
	</math>		</math>

	== General Shift Rules ==		== General Shift Rules ==
	Shift rules can jump over larger blocks. For example [[Skelet 1\|Skelet #1]] (~~<code>~~1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC~~</code>~~) exhibits the following transitions:		Shift rules can jump over larger blocks. For example [[Skelet 1\|Skelet #1]] ({{TM\|1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC}}) exhibits the following transitions:
	<math display="block">		<math display="block">
	\begin{array}{c}		\begin{array}{rcl}
	\\		\displaystyle\vphantom{\int} 011 \; \textrm{<C} & \xrightarrow{3} & \textrm{<C} \; 101 \\
	011 \; \textrm{<C} & \xrightarrow{3} & \textrm{<C} \; 101 \\		\textrm{A>} \; 110 110 & \xrightarrow{10} & 011 011 \;\textrm{A>}
	\textrm{A>} \; 110 110 & \xrightarrow{10} & 011 011 \; A>
	\end{array}		\end{array}
	</math>		</math>
	~~and so each~~ of these can be repeated an arbitrary number of times as		Each of these can be repeated an arbitrary number of times, producing the general shift rules:
	<math display="block">		<math display="block">
	\begin{array}{c}		\begin{array}{rcl}
	\\		\displaystyle\vphantom{\int}011^n \; \textrm{<C} & \xrightarrow{3n} & \textrm{<C} \; 101^n \\
	011^n \; \textrm{<C} & \xrightarrow{3n} & \textrm{<C} \; 101^n \\		\textrm{A>} \; {110 110}^n & \xrightarrow{10n} & {011 011}^n \;\textrm{A>} \\
	\textrm{A>} \; {110 110}^n & \xrightarrow{10n} & {011 011}^n \; A> \\
	\end{array}		\end{array}
	</math>		</math>
	Shift rules can also depend upon additional "local context". For example Skelet #1 also exhibits transition:		Shift rules can also depend upon additional "local context". For example, Skelet #1 also exhibits this transition:
	<math display="block">		<math display="block">
	\vphantom{\int} 01 \; \textrm{<C} \, 1 \xrightarrow{6} \textrm{<C} \, 1 \; 01		\vphantom{\int} 01 \; \textrm{<C} \; 1 \xrightarrow{6} \textrm{<C} \; 1 \; 01
	</math>		</math>
	and since the resulting config has the same "context" (a 1 ~~behind~~ the TM head), this can be repeated as well to produce the shift rule:		and since the resulting config has the same "context" (a 1 to the right of the head), this can be repeated as well to produce the shift rule:
	<math display="block">		<math display="block">
	\vphantom{\int} 01^n \; \textrm{<C} \, 1 \xrightarrow{6n} \textrm{<C} \, 1 \; 01^n.		\vphantom{\int} 01^n \; \textrm{<C} \; 1 \xrightarrow{6n} \textrm{<C} \; 1 \; 01^n.
	</math>		</math>

	== Inductive Rules ==		== Inductive Rules ==
	Shift rules can be seen as the simplest example of [[Inductive Proof System\|~~Inductive~~ rules]]. Specifically, they are Level 0 Inductive rules which only use the inductive hypothesis once: Tape rewrite rules that can be proven using induction, where each step in the proof is either a basic TM transition or an inductive application of the rule being proven ~~(but do~~ not use any other previously proven rules).		Shift rules can be seen as the simplest example of [[Inductive Proof System\|inductive rules]]. Specifically, they are Level 0 Inductive rules which only use the inductive hypothesis once: Tape rewrite rules that can be proven using induction, where each step in the proof is either a basic Turing machine transition or an inductive application of the rule being proven that does not use any other previously proven rules).

	== Simulation Acceleration ==		== Simulation Acceleration ==
	One of the main uses of shift rules is to [[Accelerated Simulator\|accelerate simulation]] of ~~TMs~~. For example, consider the simple [[~~Bouncer~~]]: {{TM\|1RB1LA_1LA1RB}} using the shift rules:		One of the main uses of shift rules is to [[Accelerated Simulator\|accelerate the simulation]] of Turing machines. For example, consider the simple [[bouncer]] {{TM\|1RB1LA_1LA1RB}} using the shift rules:
	<math display="block">\begin{array}{c}		<math display="block">\begin{array}{rcl}
	\\		\displaystyle\vphantom{\int}1^n \; \textrm{<A} & \xrightarrow{n} & \textrm{<A} \; 1^n \\
	1^n \; \textrm{<A} & \xrightarrow{n} & \textrm{<A} \; 1^n \\		\textrm{B>} \; 1^n & \xrightarrow{n} & 1^n \; \textrm{B>} \\
	\textrm{B>} \; 1^n & \xrightarrow{n} & 1^n \; B> \\
	\end{array}</math>		\end{array}</math>

	We can accelerate the simulation like this:		We can accelerate the simulation like this:
	<math display="block">\begin{array}{c}
	0^\infty \; \textrm{<A} \; 0^\infty \\		<math display="block">\begin{array}{ll}
	0^\infty \; 1 \; \textrm{B>} \; 0^\infty \\		\text{Start}{:}&0^\infty \; \textrm{<A} \; 0^\infty \\
	0^\infty \; 1 \; \textrm{<A} \; 1 \; 0^\infty \\		\text{Step 1}{:}&0^\infty \; 1 \; \textrm{B>} \; 0^\infty \\
	0^\infty \; \textrm{<A} \; 1^2 \; 0^\infty \\		\text{Step 2}{:}&0^\infty \; 1 \; \textrm{<A} \; 1 \; 0^\infty \\
	\vdots \\		\text{Step 3}{:}&0^\infty \; \textrm{<A} \; 1^2 \; 0^\infty \\
	0^\infty \; \textrm{<A} \; 1^{2n} \; 0^\infty \\		\qquad\qquad\qquad\vdots \\
	0^\infty \; 1 \; \textrm{B>} \; 1^{2n} \; 0^\infty \\		\text{Step }3n{:}&0^\infty \; \textrm{<A} \; 1^{2n} \; 0^\infty \\
	0^\infty \; 1^{2n+1} \; \textrm{B>} \; 0^\infty \\		\text{Step }3n+1{:}&0^\infty \; 1 \; \textrm{B>} \; 1^{2n} \; 0^\infty \\
	0^\infty \; 1^{2n+1} \; \textrm{<A} \; 1 \; 0^\infty \\		\text{Step }4n+1{:}&0^\infty \; 1^{2n+1} \; \textrm{B>} \; 0^\infty \\
	0^\infty \; \textrm{<A} \; 1^{2n+2} \; 0^\infty \\		\text{Step }4n+2{:}&0^\infty \; 1^{2n+1} \; \textrm{<A} \; 1 \; 0^\infty \\
	\vdots \\		\text{Step }5n+3{:}&0^\infty \; \textrm{<A} \; 1^{2n+2} \; 0^\infty \\
			\qquad\qquad\qquad\vdots \\
	\end{array}</math>		\end{array}</math>
			In this case, they allow one to use <math>n</math> simulator steps to simulate <math>O(n^2)</math> base steps, which is the best-case speedup using only shift rules. More general [[Inductive Proof System\|inductive rules]] that can further accelerate a Turing machine's simulation may build on top of shift rules.

	In this case, this allows simulating <math>O(n^2)</math> base TM steps using only <math>n</math> simulator steps which is the best-case speedup using only shift rules. But further acceleration can also be built on top of this by using more general [[Inductive Proof System\|inductive rules]].		== Moving across an infinite line of 0s ==
			Any Turing machine that has at least one of the two following types of shift rules:
	== ~~Prove Non-halting~~ ==		<math display="block">
	~~Shift~~ rules ~~can be used to prove non-halting. For example, if you have a shift rule~~ <math display="block">\textrm{S>} \; 0^n \to 1^n \; \textrm{S>}</math>and the ~~TM reaches~~ configuration<math ~~display="block"~~>\textrm{S>} \; 0^\infty</math>~~then it~~ is ~~guaranteed to never halt~~, ~~because this rule will repeat forever. This is an example of~~ a [[~~Translated Cycler~~]].		\displaystyle\vphantom{\int}t\;\textrm{S>} \; 0^n \to r'\;t\;\textrm{S>}\qquad\text{or}\qquad \displaystyle\vphantom{\int}0^n\;\textrm{<S}\;t\to \textrm{<S}\;t\;r',
			</math>
			and which eventually reaches the configuration <math>t\;\textrm{S>}\;0^\infty</math> (for the first rule) or <math>0^\infty\;\textrm{<S}\;t</math> (for the second rule) is non-halting, becoming a [[translated cycler]].

Sligocki: /* Simulation Acceleration */ Fix TM example (it was flipped)

2025-04-12T14:42:23Z

Simulation Acceleration: Fix TM example (it was flipped)

← Older revision		Revision as of 14:42, 12 April 2025
Line 47:		Line 47:

	== Simulation Acceleration ==		== Simulation Acceleration ==
	One of the main uses of shift rules is to [[Accelerated Simulator\|accelerate simulation]] of TMs. For example, consider the simple [[Bouncer]]: ~~[https://bbchallenge.org/1RB1LA_1LA1RB <code>~~1RB1LA_1LA1RB~~</code>]~~ using the shift rules:<math display="block">\begin{array}{c}		One of the main uses of shift rules is to [[Accelerated Simulator\|accelerate simulation]] of TMs. For example, consider the simple [[Bouncer]]: {{TM\|1RB1LA_1LA1RB}} using the shift rules:
			<math display="block">\begin{array}{c}
	\\		\\
	\textrm{A>} ~~\; 1^n~~ & \xrightarrow{n} & 1^n ~~\; A>~~ \\		1^n \; \textrm{<A} & \xrightarrow{n} & \textrm{<A} \; 1^n \\
	~~1^n \;~~ \textrm{<B} & \xrightarrow{n} & ~~\textrm{<B} \;~~ 1^n \\		\textrm{B>} \; 1^n & \xrightarrow{n} & 1^n \; B> \\
	\end{array}</math>We can accelerate the simulation like this:<math display="block">\begin{array}{c}		\end{array}</math>
	0^\infty \; \textrm{A>} \; 0^\infty \\
	0^\infty \; \textrm{<B} ~~\; 1~~ \; 0^\infty \\		We can accelerate the simulation like this:
	0^\infty \; 1 \; \textrm{A>} \; 1 \; 0^\infty \\		<math display="block">\begin{array}{c}
	0^\infty ~~\; 1^2~~ \; \textrm{A>} \; 0^\infty \\		0^\infty \; \textrm{<A} \; 0^\infty \\
			0^\infty \; 1 \; \textrm{B>} \; 0^\infty \\
			0^\infty \; 1 \; \textrm{<A} \; 1 \; 0^\infty \\
			0^\infty \; \textrm{<A} \; 1^2 \; 0^\infty \\
	\vdots \\		\vdots \\
	0^\infty \; 1^{2n} \; ~~\textrm~~{A>} \; 0^\infty \\		0^\infty \; \textrm{<A} \; 1^{2n} \; 0^\infty \\
	0^\infty \; 1~~^{2n}~~ \; \textrm{<B} \; 1 \; 0^\infty \\		0^\infty \; 1 \; \textrm{B>} \; 1^{2n} \; 0^\infty \\
	0^\infty ~~\; \textrm{<B}~~ \; 1^{2n+1} \; 0^\infty \\		0^\infty \; 1^{2n+1} \; \textrm{B>} \; 0^\infty \\
	0^\infty \; 1 \; \textrm{A>} \; 1~~^{2n+1}~~ \; 0^\infty \\		0^\infty \; 1^{2n+1} \; \textrm{<A} \; 1 \; 0^\infty \\
	0^\infty \; 1^{2n+2~~} \; \textrm{A>~~} \; 0^\infty \\		0^\infty \; \textrm{<A} \; 1^{2n+2} \; 0^\infty \\
	\vdots \\		\vdots \\
	\end{array}</math>In this case, this allows simulating <math>O(n^2)</math> base TM steps using only <math>n</math> simulator steps which is the best-case speedup using only shift rules. But further acceleration can also be built on top of this by using more general [[Inductive Proof System\|inductive rules]].		\end{array}</math>

			In this case, this allows simulating <math>O(n^2)</math> base TM steps using only <math>n</math> simulator steps which is the best-case speedup using only shift rules. But further acceleration can also be built on top of this by using more general [[Inductive Proof System\|inductive rules]].

	== Prove Non-halting ==		== Prove Non-halting ==
	Shift rules can be used to prove non-halting. For example, if you have a shift rule <math display="block">\textrm{S>} \; 0^n \to 1^n \; \textrm{S>}</math>and the TM reaches configuration<math display="block">\textrm{S>} \; 0^\infty</math>then it is guaranteed to never halt, because this rule will repeat forever. This is an example of a [[Translated Cycler]].		Shift rules can be used to prove non-halting. For example, if you have a shift rule <math display="block">\textrm{S>} \; 0^n \to 1^n \; \textrm{S>}</math>and the TM reaches configuration<math display="block">\textrm{S>} \; 0^\infty</math>then it is guaranteed to never halt, because this rule will repeat forever. This is an example of a [[Translated Cycler]].

Mxdys: fix typo

2024-07-15T06:02:47Z

fix typo

← Older revision		Revision as of 06:02, 15 July 2024
Line 14:		Line 14:
	Similarly, if the machine transitions from <math> r \; \textrm{<S} \; t</math> to <math>\textrm{<S} \; t r'</math>, then we have a ''left'' shift rule		Similarly, if the machine transitions from <math> r \; \textrm{<S} \; t</math> to <math>\textrm{<S} \; t r'</math>, then we have a ''left'' shift rule
	<math display="block">		<math display="block">
	\vphantom{\int} r \; \textrm{<S} \; t \to \textrm{<S} \; r' t.		\vphantom{\int} r \; \textrm{<S} \; t \to \textrm{<S} \; t r'.
	</math>		</math>

Sligocki: /* Simulation Acceleration */

2024-06-16T03:26:36Z

Simulation Acceleration

← Older revision		Revision as of 03:26, 16 June 2024
Line 47:		Line 47:

	== Simulation Acceleration ==		== Simulation Acceleration ==
	One of the main uses of shift rules is to accelerate simulation of TMs. For example, consider the simple [[Bouncer]]: [https://bbchallenge.org/1RB1LA_1LA1RB <code>1RB1LA_1LA1RB</code>] using the shift rules:<math display="block">\begin{array}{c}		One of the main uses of shift rules is to [[Accelerated Simulator\|accelerate simulation]] of TMs. For example, consider the simple [[Bouncer]]: [https://bbchallenge.org/1RB1LA_1LA1RB <code>1RB1LA_1LA1RB</code>] using the shift rules:<math display="block">\begin{array}{c}
	\\		\\
	\textrm{A>} \; 1^n & \xrightarrow{n} & 1^n \; A> \\		\textrm{A>} \; 1^n & \xrightarrow{n} & 1^n \; A> \\

Sligocki: /* Simulation Acceleration */

2024-06-16T03:25:49Z

Simulation Acceleration

← Older revision		Revision as of 03:25, 16 June 2024
Line 44:		Line 44:

	== Inductive Rules ==		== Inductive Rules ==
	Shift rules can be seen as the simplest example of [[Inductive ~~rule~~\|Inductive rules]]. Specifically, they are Level 0 Inductive rules which only use the inductive hypothesis once: Tape rewrite rules that can be proven using induction, where each step in the proof is either a basic TM transition or an inductive application of the rule being proven (but do not use any other previously proven rules).		Shift rules can be seen as the simplest example of [[Inductive Proof System\|Inductive rules]]. Specifically, they are Level 0 Inductive rules which only use the inductive hypothesis once: Tape rewrite rules that can be proven using induction, where each step in the proof is either a basic TM transition or an inductive application of the rule being proven (but do not use any other previously proven rules).

	== Simulation Acceleration ==		== Simulation Acceleration ==
Line 63:		Line 63:
	0^\infty \; 1^{2n+2} \; \textrm{A>} \; 0^\infty \\		0^\infty \; 1^{2n+2} \; \textrm{A>} \; 0^\infty \\
	\vdots \\		\vdots \\
	\end{array}</math>In this case, this allows simulating <math>O(n^2)</math> base TM steps using only <math>n</math> simulator steps which is the best-case speedup using only shift rules. But further acceleration can also be built on top of this by using more general [[inductive rules]].		\end{array}</math>In this case, this allows simulating <math>O(n^2)</math> base TM steps using only <math>n</math> simulator steps which is the best-case speedup using only shift rules. But further acceleration can also be built on top of this by using more general [[Inductive Proof System\|inductive rules]].

	== Prove Non-halting ==		== Prove Non-halting ==
	Shift rules can be used to prove non-halting. For example, if you have a shift rule <math display="block">\textrm{S>} \; 0^n \to 1^n \; \textrm{S>}</math>and the TM reaches configuration<math display="block">\textrm{S>} \; 0^\infty</math>then it is guaranteed to never halt, because this rule will repeat forever. This is an example of a [[Translated Cycler]].		Shift rules can be used to prove non-halting. For example, if you have a shift rule <math display="block">\textrm{S>} \; 0^n \to 1^n \; \textrm{S>}</math>and the TM reaches configuration<math display="block">\textrm{S>} \; 0^\infty</math>then it is guaranteed to never halt, because this rule will repeat forever. This is an example of a [[Translated Cycler]].