Turing Machines

General Overview

A Turing machine (TM) is a hypothetical machine (computing device) first conceived by the English mathematician Alan Turing in 1936 to help solve a specific question in mathematical logic. Despite its simplicity, the machine can simulate any computer algorithm, no matter how complicated it may be.

We may visualize a TM as follows [1]:

The machine consists of a finite control (equivalent to a CPU in modern day computers), which can be in any of a finite set of states. There is a tape divided into squares or cells ; each cell can hold any one of a finite number of symbols.

Initially the input, which is a finite-length string of symbols chosen from the input alphabet, is placed on the tape. All other tape cells, extending infinitely to the left and right, hold a special symbol called the blank. The blank is a tape symbol but not an input symbol.

There is a tape head that is always positioned at one of the tape cells. The TM is said to be scanning that cell. Initially, by convention, the tape head is at the leftmost cell that holds the input.

A move of the TM is a function of the state of the finite control and the tape symbol scanned. In one move the TM will:

1. Change state. The next state optionally may be the same as the current state.

2. Write a tape symbol in the cell scanned. This tape symbol replaces whatever symbol was in that cell. Optionally, the symbol written may be the same as the symbol currently there.

3. Move the tape head left or right.

Formally, a TM is defined by the 7-tuple \(M = (Q, \Sigma, \Gamma, \delta, q_0, B, F) \), where:

• \(Q\) : The finite set of states of the finite control.

• \(\Sigma\) : The finite set of input symbols.

• \(\Gamma\) : The complete set of tape symbols \((\Sigma \subset \Gamma)\).

• \(\delta\) : \((Q - F) \times \Gamma \rightarrow Q \times \Gamma \times \{ L, R \} \) is the transition function.

  The arguments of \(\delta(q, X)\) are a state \(q\) and a tape symbol \(X\). The value of \(\delta(q, X)\), if it is defined, is a triple \((Y, D, p)\), where:

  • \(Y\) is the symbol \((Y \in \Gamma)\), written in the cell being scanned, replacing whatever symbol was there.

  • \(D\) is a direction, either \(L\) or \(R\), standing for “left” or “right”, respectively, and telling us the direction in which the head moves.

  • \(p\) is the next state \((p \in Q)\).

  Note that if \(\delta(q, X)\) is not defined, then the machine halts and the input is rejected.

• \(q_0\) : The start state \((q_0 \in Q)\), in which the finite control is found initially.

• \(B\) : The blank symbol, which is not an input symbol \((B \in \Gamma , B \notin \Sigma)\). The blank appears initially in all but the finite number of initial cells that hold input symbols.

• \(F\) : The set of final or accepting states \((F \subseteq Q)\). A TM always halts when it is in an accepting state.

Let \(M\) be a TM and \(w\) a string.

• \(M\) accepts \(w\) if it enters an accept state when run on \(w\).

• \(M\) rejects \(w\) if it enters the reject state when run on \(w\).

• \(M\) loops infinitely on \(w\) if when run on \(w\) it never enters the accept or reject states.

• \(M\) halts on \(w\) if it accepts or rejects \(w\).

TM Example

Let’s define a TM that accepts the language \(\{ a^n \; | \; n \ge 0, n \bmod 2 = 0\}\). In other words, the TM should accept strings that contain a sequence with an even number of \(a\)’s.

The formal specification of this Turing machine \(M\) is:

$$ M = (\{q_0, q_1, q_2 \}, \{ a \}, \{ B, a \}, \delta, q_0, B, \{ q_2\} ) $$

where \(\delta\) is given by the following table:

State	Symbol
	\(a\)	\(B\)
\(q_0\)	\((a, R, q_1)\)	\((B, L, q_2)\)
\(q_1\)	\((a, R, q_0)\)
\(q_2\)

We can alternatively represent \(\delta\) using a state diagram as shown below [1]:

The diagram consists a set of nodes corresponding to the states of the TM. An arc from state \(q\) to state \(p\) is labeled by one or more items of the form \(X/Y;D\), where \(X\) and \(Y\) are tape symbols, and \(D\) is a direction, either \(L\) or \(R\). That is, whenever  \(\delta(q,X) = (Y, D, p)\), we find the label \(X/Y;D\) on the arc from \(q\) to \(p\). Also, in the above diagram the blank symbol \(B\) is represented with an underscore (_).

References

• [1] Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey. Introduction to Automata Theory, Languages, and Computation, 3rd. Edition. Pearson Education, 2007. ISBN: 9780321455369