Low-level Description of a Turing Machine

A low-level (or formal) description of a Turing Machine (TM) to recognize a language involves defining all the elements in the 7-tuple

    \begin{equation*} (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject}) \end{equation*}

Consider the following language

    \begin{equation*} L = \{ w\#w | w \in \{0, 1\}^* \} \end{equation*}


Here is the idea behind building a TM to recognize the above language.

  1. Scan the input tape to be sure that it contains a single \#. If not, reject.
  2. Zig-zag across the tape to corresponding positions on either side of \#to check whether these positions contain the same symbol. If they do not, reject. Cross off the symbols as they are checked.
  3. When all symbols to the left of \#have been crossed off, check for the remaining symbols to the right of \#. If any symbol remain, reject; otherwise accept.

When the idea explains in detail how the tape is modified, it is called a High-Level Description. This High-Level description can be converted into a formal description.


The input alphabet \Sigma will be \{0, 1 \#\} as defined in the language.

A new symbol (x) is needed to keep track of the crossed off symbols. Thus, the tape alphabet \Gamma will be \{0, 1 \#, \textvisiblespace, x \}.

Transition Function

The transition state diagram for the above implementation is shown below. The red path matches the 0s on either side of the \#.. The blue path matches the 1s on either side of the \#.. The orange path brings the tape-head back to the first uncrossed symbol. The black path checks if the count of the crossed out symbols match.

A note about the reject state

The state q_{reject} is not shown here. It is assumed that all undefined transitions (to ensure that the transition function is a total function) go to q_{reject}. For example q_7 has no transition on the symbol 0 in the diagram above. It goes to q_{reject}.

In essence, we only care about ensuring that the strings that are indeed accepted end up in q_{accept}. All other strings that do not match the pattern get rejected. There is no case where the machine will run forever.

Formal Description

Putting it all together, the low-level (formal) description of the TM to recognize the language L will be

    \begin{equation*} (\{q_0, q_1, q_2, q_3, q_4, q_5, q_6, q_7, q_{accept}, q_{reject}\}, \{0, 1 \#\}, \{0, 1 \#, \textvisiblespace, x \}, \delta, q_0, q_{accept}, q_{reject}) \end{equation*}

where the transition function \delta can be extracted from the transition diagram above.


Leave a Reply

Your email address will not be published. Required fields are marked *