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*}$

Idea

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

Scan the input tape to be sure that it contains a single $\#$ . If not, reject.
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.
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.

Alphabet

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 $0$ s on either side of the $\#$ .. The blue path matches the $1$ s 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.

References

https://www.ics.uci.edu/~goodrich/teach/cs162/notes/turing2.pdf

The Beard Sage