Clockwise Turing machine

A clockwise Turing machine is a Turing machine variant where the tape is circular and only clockwise moves are allowed.

Neary and Woods present the following definition for the concept:

• Clockwise Turing machine definitions have
  • A set of states $Q$
  • A set of symbols $\Sigma$
  • A transition function $f:Q\times \Sigma \rightarrow \lbrace \Sigma \cup \Sigma \Sigma \rbrace \times Q$
  • A starting state $q_{1}\in Q$
  • A halting state $q_{|Q|}\in Q$
• The transition function
  • Is defined for all states in $Q$ except for the halting state $q_{|Q|}$
  • Maps the pair of (current state, currently read symbol) to (symbol or symbol pair, next state)

Execution proceeds as one would expect for a normal Turing machine, with the following differences:

• The tape is circular, the head/pointer's position is modulo the size of the tape
• The head moves clockwise/rightwards during every state transition
• A state transition can either overwrite the current cell (corresponding to a $\Sigma \times Q$ rule) or split the cell in two, overwriting each half with a symbol (corresponding to a $\Sigma \Sigma \times Q$ rule)

Neary and Woods prove this model Turing complete in their paper. They reduce a Turing machine model where every transition must result in a move (which is trivially Turing complete) into the clockwise model. They do this by having there be two ends of the tape which are right next to each other on the circle. These ends are marked with a special symbol, each, $\sigma _{l}$ for the left end and $\sigma _{r}$ for the right. These symbols allow for the simulation to expand the tape whenever the simulated machine reaches the boundaries. While rightward/clockwise moves are simple, nothing special is required, leftward/counterclockwise moves are more difficult. Another symbol is used to manage such moves, $\sigma _{m}$. Leftward moves place this symbol down, then proceed in a loop moving the contents of every single cell over by one, stopping when the marker is overwritten. This has the effect of moving the head left by one cell.

Clockwise Turing machines are relatively ergonomic to implement in tag systems.

See also

• Cyclic tag system