Head shifting and symbol writing TM

These are the two kinds of elementary Turing machines (Lewis and Papadimitriou), from which larger machines are built by composition.

Symbol-writing machines

For each symbol a ∈ Γ (including the blank ⊔) there is a machine, also written a, that writes a in the cell under the head and halts. The head does not move.

Formally, it has states {q0, h}, and δ(q0, x) = (h, a, S) for every x ∈ Γ. Example: the machine "1" replaces whatever symbol is scanned by 1. The machine "⊔" erases the cell.

Head-moving (head-shifting) machines

Two machines change only the head position and leave the tape contents unchanged:

• R moves the head one cell to the right and halts: δ(q0, x) = (h, x, R) for all x.
• L moves the head one cell to the left and halts: δ(q0, x) = (h, x, L) for all x.

  Before:  ... a [b] c ...
  R   :    ... a  b [c] ...
  L   :    ... [a] b  c ...
  "x" :    ... a [x] c ...   (b overwritten by x)

Use

These machines are combined with arrows (conditions on the scanned symbol) to give larger machines. For example, R⊔ means "move right until a blank is found" and L⊔ means "move left until a blank is found". Any TM can be described as such a combination, which is why they are called the basic building blocks of Turing machines.