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 Turing machine with the transition $(\text{S},1)\to (0,R,\text{S})$ then using directed head notation: $$\phantom{\int }\text{S}\text{<mo>></mo>}{1}^n\stackrel{n}{\to }{0}^n\text{S}\text{<mo>></mo>}$$ In other words, if the machine is in state $\text{S}$ and the head is 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^{\prime }$ in the alphabet of the Turing machine in question, and assume that for some state $\text{S}$ the machine transitions from $t\text{S}\text{<mo>></mo>}r$ to $r^{\prime }t\text{S}\text{<mo>></mo>}$. Then we have a right shift rule $$\phantom{\int }t\text{S}\text{<mo>></mo>}r\to r^{\prime }t\text{S}\text{<mo>></mo>}.$$ Similarly, if the machine transitions from $r\text{<mo><</mo>}\text{S}t$ to $\text{<mo><</mo>}\text{S}t{r}^{\prime }$, then we have a left shift rule $$\phantom{\int }r\text{<mo><</mo>}\text{S}t\to \text{<mo><</mo>}\text{S}t{r}^{\prime }.$$

General Shift Rules

Shift rules can jump over larger blocks. For example Skelet #1 (1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC (bbch)) exhibits the following transitions: $$\begin{array}{rcl}\phantom{\int }011\text{<mo><</mo>}\text{C}& \stackrel{3}{\to }& \text{<mo><</mo>}\text{C}101\\ \text{A}\text{<mo>></mo>}110110& \stackrel{10}{\to }& 011011\text{A}\text{<mo>></mo>}\end{array}$$ Each of these can be repeated an arbitrary number of times, producing the general shift rules: $$\begin{array}{rcl}\phantom{\int }011^n\text{<mo><</mo>}\text{C}& \stackrel{3n}{\to }& \text{<mo><</mo>}\text{C}101^n\\ \text{A}\text{<mo>></mo>}{110110}^n& \stackrel{10n}{\to }& {011011}^n\text{A}\text{<mo>></mo>}\\ \end{array}$$ Shift rules can also depend upon additional "local context". For example, Skelet #1 also exhibits this transition: $$\phantom{\int }01\text{<mo><</mo>}\text{C}1\stackrel{6}{\to }\text{<mo><</mo>}\text{C}101$$ 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: $$\phantom{\int }01^n\text{<mo><</mo>}\text{C}1\stackrel{6n}{\to }\text{<mo><</mo>}\text{C}101^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 Turing machine transition or an inductive application of the rule being proven that does not use any other previously proven rules).

Simulation Acceleration

One of the main uses of shift rules is to accelerate the simulation of Turing machines. For example, consider the simple bouncer 1RB1LA_1LA1RB (bbch) using the shift rules: $$\begin{array}{rcl}\phantom{\int }{1}^n\text{<mo><</mo>}\text{A}& \stackrel{n}{\to }& \text{<mo><</mo>}\text{A}{1}^n\\ \text{B}\text{<mo>></mo>}{1}^n& \stackrel{n}{\to }& 1^n\text{B}\text{<mo>></mo>}\\ \end{array}$$

We can accelerate the simulation like this:

$$\begin{array}{ll}\text{Start}:& 0^{\mathrm{\infty }}\text{<mo><</mo>}\text{A}{0}^{\mathrm{\infty }}\\ \text{Step 1}:& 0^{\mathrm{\infty }}1\text{B}\text{<mo>></mo>}{0}^{\mathrm{\infty }}\\ \text{Step 2}:& 0^{\mathrm{\infty }}1\text{<mo><</mo>}\text{A}10^{\mathrm{\infty }}\\ \text{Step 3}:& 0^{\mathrm{\infty }}\text{<mo><</mo>}\text{A}{1}^2{0}^{\mathrm{\infty }}\\ ⋮\\ \text{Step }2n^2+n:& 0^{\mathrm{\infty }}\text{<mo><</mo>}\text{A}{1}^{2n}{0}^{\mathrm{\infty }}\\ \text{Step }2n^2+n+1:& 0^{\mathrm{\infty }}1\text{B}\text{<mo>></mo>}{1}^{2n}{0}^{\mathrm{\infty }}\\ \text{Step }2n^2+3n+1:& 0^{\mathrm{\infty }}{1}^{2n+1}\text{B}\text{<mo>></mo>}{0}^{\mathrm{\infty }}\\ \text{Step }2n^2+3n+2:& 0^{\mathrm{\infty }}{1}^{2n+1}\text{<mo><</mo>}\text{A}10^{\mathrm{\infty }}\\ \text{Step }2n^2+5n+3:& 0^{\mathrm{\infty }}\text{<mo><</mo>}\text{A}{1}^{2n+2}{0}^{\mathrm{\infty }}\\ ⋮\\ \end{array}$$ In this case, they allow one to use $n$ simulator steps to simulate $O(n^2)$ base steps, which is the best-case speedup using only shift rules. More general inductive rules that can further accelerate a Turing machine's simulation may build on top of shift rules.

Moving across an infinite line of 0s

Any Turing machine that has at least one of the two following types of shift rules: $$\phantom{\int }t\text{S}\text{<mo>></mo>}{0}^n\to r^{\prime }t\text{S}\text{<mo>></mo>}\text{or}\phantom{\int }{0}^n\text{<mo><</mo>}\text{S}t\to \text{<mo><</mo>}\text{S}t{r}^{\prime },$$ and which eventually reaches the configuration $t\text{S}\text{<mo>></mo>}{0}^{\mathrm{\infty }}$ (for the first rule) or $0^{\mathrm{\infty }}\text{<mo><</mo>}\text{S}t$ (for the second rule) is non-halting, becoming a translated cycler.