Shift rule

2024-06-15T11:30:24Z

Savask: Added the definition of a shift rule, tried to correct some vertical spaces

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]]:
<math display="block">
\vphantom{\int}\textrm{S>} \; 1^n \xrightarrow{n} 0^n \; \textrm{S>}
</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.

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
<math display="block">
\vphantom{\int} t \; \textrm{S>} \; r \to r' t \; \textrm{S>}.
</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
<math display="block">
\vphantom{\int} r \; \textrm{<S} \; t \to \textrm{<S} \; r' t.
</math>

== 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:
<math display="block">
\begin{array}{c}
\\
011 \; \textrm{<C} & \xrightarrow{3} & \textrm{<C} \; 101 \\
\textrm{A>} \; 110 110 & \xrightarrow{10} & 011 011 \; A>
\end{array}
</math>
and so each of these can be repeated an arbitrary number of times as
<math display="block">
\begin{array}{c}
\\
011^n \; \textrm{<C} & \xrightarrow{3n} & \textrm{<C} \; 101^n \\
\textrm{A>} \; {110 110}^n & \xrightarrow{10n} & {011 011}^n \; A> \\
\end{array}
</math>
Shift rules can also depend upon additional "local context". For example Skelet #1 also exhibits transition:
<math display="block">
\vphantom{\int} 01 \; \textrm{<C} \, 1 \xrightarrow{6} \textrm{<C} \, 1 \; 01
</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:
<math display="block">
\vphantom{\int} 01^n \; \textrm{<C} \, 1 \xrightarrow{6n} \textrm{<C} \, 1 \; 01^n.
</math>

== 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).

== 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}
\\
\textrm{A>} \; 1^n & \xrightarrow{n} & 1^n \; A> \\
1^n \; \textrm{<B} & \xrightarrow{n} & \textrm{<B} \; 1^n \\
\end{array}</math>We can accelerate the simulation like this:<math display="block">\begin{array}{c}
0^\infty \; \textrm{A>} \; 0^\infty \\
0^\infty \; \textrm{<B} \; 1 \; 0^\infty \\
0^\infty \; 1 \; \textrm{A>} \; 1 \; 0^\infty \\
0^\infty \; 1^2 \; \textrm{A>} \; 0^\infty \\
\vdots \\
0^\infty \; 1^{2n} \; \textrm{A>} \; 0^\infty \\
0^\infty \; 1^{2n} \; \textrm{<B} \; 1 \; 0^\infty \\
0^\infty \; \textrm{<B} \; 1^{2n+1} \; 0^\infty \\
0^\infty \; 1 \; \textrm{A>} \; 1^{2n+1} \; 0^\infty \\
0^\infty \; 1^{2n+2} \; \textrm{A>} \; 0^\infty \\
\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]].

== 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]].

BusyBeaverWiki - User contributions [en]

Shift rule