Directed head notation

Directed head notation is a notation for specifying a Turing machine configuration using tape compression and a TM head which "points" either to the left or right. Directed head notation may be used for a complete tape configuration

$$0^{\infty }\;1\;{\textrm {<B}}\;0^{3}\;13^{10}\;2\;0^{\infty }$$

or for a partial configuration

$$101\;{\textrm {A>}}\;1^{n}$$

Tape Compression

This notation supports run-length encoding for tape compression using "exponents". Given a "word" (sequence of tape symbols) $w$ and a count $n$, $w^{n}$ represents $n$ repetitions of $w$ concatenated. So for example, $2^{4}=2222$ and $10^{3}=101010$.

It is important to note here that the words "2" and "10" in these examples are sequences of tape symbols and not integers and that the counts "4" and "3" are integer repetition counts, not representing integer exponentiation. It is perhaps unfortunate that these compressed blocks look identical to integer mathematical expressions. Generally, it should be obvious from the context that this is a tape configuration and not a math expression.

Segments of the tape may also be specified without exponents which represent unrepeated (or 1 repeat) of that segment. The notation $0^{\infty }$ is used to represent the infinite sequence of blank symbols at either end of a configuration. In general, there will be many different notations for identical tape segments. For example:

$$0^{\infty }\;121212=0^{\infty }\;12\;12\;12=0^{\infty }\;12^{3}=0^{\infty }\;01\;21^{2}\;2$$

Directed Head

Traditionally, the Turing machine head is considered to be located "on" a tape cell, for example some common traditional notation for a TM configuration include:

$$\dots 0110{\underset {A}{\underline {2}}}01110\dots$$

or

$$\dots 0110(A2)01110\dots$$

which indicate that the TM is in state A and currently positioned on the tape cell containing the 2. In these notations there are 3 groupings of symbols: those to the left ($\dots 0110$), those to the right ($01110\dots$) and the single current symbol (2).

In directed head notation, we instead conceptualize the TM head as in the process of moving from one tape cell to another. So the above configuration could be represented by either

$$\dots 0110\;{\textrm {A>}}\;201110\dots$$

or

$$\dots 01102\;{\textrm {<A}}\;01110\dots$$

depending on which direction it moved immediately previous to this config. In many contexts, these may be considered equivalent configurations (since the forward behavior is identical for either). Here the notation "A>" means that the TM is in state A moving toward the right and "<A" means that it is moving to the left. The "current symbol" is the symbol "small end" of these "directed head" arrows.

Partial Configurations

A directed head configuration includes a directed head and zero or more tape segments on each side. If it includes $0^{\infty }$ at both ends, then it is a complete configuration (specifying precisely the entire tape), otherwise it is a partial configuration (specifying only a limited context around the TM head). For example, the partial configuration

$$101\;{\textrm {C>}}\;1^{3}$$

matches any of these complete configurations

$${\begin{array}{rcl}0^{\infty }\;101&{\textrm {C>}}&1^{3}\;0^{\infty }\\0^{\infty }\;11101&{\textrm {C>}}&1^{8}\;0^{\infty }\\0^{\infty }\;01^{3}&{\textrm {C>}}&11^{2}\;0^{\infty }\\\end{array}}$$

Partial configurations may have no segments specified even on the side the TM head is facing. For example

$${\textrm {<C}}\;101$$

is a valid partial configuration. In these cases, we cannot tell what the "current symbol" is until we know the complete configuration. These configurations are common as the result of configuration transitions as described below.

Configuration Transitions

One of the most common use cases for directed head notation is for specifying configuration transition rules. For example, the rule

$${\begin{array}{c}\\0^{\infty }\;011\;{\textrm {<C}}\;0^{\infty }\;\xrightarrow {3} \;0^{\infty }\;{\textrm {<C}}\;101\;0^{\infty }\\\end{array}}$$

indicates that if the TM starts in config $0^{\infty }\;011\;{\textrm {<C}}\;0^{\infty }$, 3 steps later it will be in configuration $0^{\infty }\;{\textrm {<C}}\;101\;0^{\infty }$. It is common to define these rules for partial configurations. For example,

$${\begin{array}{c}\\011\;{\textrm {<C}}\;\xrightarrow {3} \;{\textrm {<C}}\;101\\\end{array}}$$

which means that for any complete configuration $w\;011\;{\textrm {<C}}\;u$ (where $w,u$ are any valid left and right half-tapes), 3 steps later it will be in configuration $w\;{\textrm {<C}}\;101\;u$.

Transition rules become especially useful once you use induction to prove them over arbitrary repetition counts. For example, the previous transition rule can prove this shift rule for all $n\geq 0$:

$${\begin{array}{c}\\011^{n}\;{\textrm {<C}}\;\xrightarrow {3n} \;{\textrm {<C}}\;101^{n}\\\end{array}}$$