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^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD"><mo><</mo>B</mrow>}{0}^{3}13^{10}20^{\mathrm{\infty }}$$

or for a partial configuration $$101\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{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^{\mathrm{\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^{\mathrm{\infty }}121212=0^{\mathrm{\infty }}121212=0^{\mathrm{\infty }}12^3=0^{\mathrm{\infty }}0121^{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 configurations include:$$\dots 0110\underset{A}{\underset{\_}{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\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}201110\dots$$or$$\dots 01102\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}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.

Configurations

A directed head configuration includes a directed head and zero or more tape segments on each side.