Shift rule

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 $(S,1)\to (0,R,S)$ then using directed head notation:

$${\vphantom {\int }}{\textrm {S>}}\;1^{n}\xrightarrow {n} 0^{n}\;{\textrm {S>}}$$

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 $t$, $r$ and $r'$ in the alphabet of the Turing machine in question, and assume that for some state S the machine transitions from $t\;{\textrm {S>}}\;r$ to $r't\;{\textrm {S>}}$. Then we have a right shift rule

$${\vphantom {\int }}t\;{\textrm {S>}}\;r\to r't\;{\textrm {S>}}.$$

Similarly, if the machine transitions from $r\;{\textrm {<S}}\;t$ to ${\textrm {<S}}\;tr'$, then we have a left shift rule

$${\vphantom {\int }}r\;{\textrm {<S}}\;t\to {\textrm {<S}}\;tr'.$$

General Shift Rules

Shift rules can jump over larger blocks. For example Skelet #1 (1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC) exhibits the following transitions:

$${\begin{array}{c}\\011\;{\textrm {<C}}&\xrightarrow {3} &{\textrm {<C}}\;101\\{\textrm {A>}}\;110110&\xrightarrow {10} &011011\;A>\end{array}}$$

and so each of these can be repeated an arbitrary number of times as

$${\begin{array}{c}\\011^{n}\;{\textrm {<C}}&\xrightarrow {3n} &{\textrm {<C}}\;101^{n}\\{\textrm {A>}}\;{110110}^{n}&\xrightarrow {10n} &{011011}^{n}\;A>\\\end{array}}$$

Shift rules can also depend upon additional "local context". For example Skelet #1 also exhibits transition:

$${\vphantom {\int }}01\;{\textrm {<C}}\,1\xrightarrow {6} {\textrm {<C}}\,1\;01$$

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:

$${\vphantom {\int }}01^{n}\;{\textrm {<C}}\,1\xrightarrow {6n} {\textrm {<C}}\,1\;01^{n}.$$

Inductive Rules

Shift rules can be seen as the simplest example of 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: 1RB1LA_1LA1RB (bbch) using the shift rules:

$${\begin{array}{c}\\1^{n}\;{\textrm {<A}}&\xrightarrow {n} &{\textrm {<A}}\;1^{n}\\{\textrm {B>}}\;1^{n}&\xrightarrow {n} &1^{n}\;B>\\\end{array}}$$

We can accelerate the simulation like this:

$${\begin{array}{c}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 \\0^{\infty }\;{\textrm {<A}}\;1^{2n}\;0^{\infty }\\0^{\infty }\;1\;{\textrm {B>}}\;1^{2n}\;0^{\infty }\\0^{\infty }\;1^{2n+1}\;{\textrm {B>}}\;0^{\infty }\\0^{\infty }\;1^{2n+1}\;{\textrm {<A}}\;1\;0^{\infty }\\0^{\infty }\;{\textrm {<A}}\;1^{2n+2}\;0^{\infty }\\\vdots \\\end{array}}$$

In this case, this allows simulating $O(n^{2})$ base TM steps using only $n$ 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

$${\textrm {S>}}\;0^{n}\to 1^{n}\;{\textrm {S>}}$$

and the TM reaches configuration

$${\textrm {S>}}\;0^{\infty }$$

then it is guaranteed to never halt, because this rule will repeat forever. This is an example of a Translated Cycler.