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:

$${\begin{array}{l}\\{\textrm {S>}}\;1^{n}\xrightarrow {n} 0^{n}\;S>\\\end{array}}$$

In other words, if the TM is in state S reading the leftmost of a sequence of n 1s, then n steps later it will have moved to the right of this entire sequence of 1s, converting them all to 0s.

General Shift Rules

Shift rules can also 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:

$${\begin{array}{c}\\01\;{\textrm {<C}}\,1&\xrightarrow {6} &{\textrm {<C}}\,1\;01\\\end{array}}$$

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:

$${\begin{array}{c}\\01^{n}\;{\textrm {<C}}\,1&\xrightarrow {6n} &{\textrm {<C}}\,1\;01^{n}\\\end{array}}$$

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