19. Turing Machines
Turing machines provide a model of computation that, as we will see, has two notable characteristics:
- It is very simple, so that we can analyze Turing machines and prove important facts about what they can and cannot do.
- It is very powerful, so that it captures the notion of computability in a general and far-reaching way.
Description of Turing Machines
Turing machines consist of two main components:
- A tape, which consists of an infinitely long sequence of individual squares, each of which is either blank or contains a single symbol from some finite tape alphabet; and
- A machine that has a tape head positioned over one of the squares of the tape and a finite number of (internal) states.
Turing machines take some input in the form of a string over an input alphabet that is a subset of the tape alphabet. The input is initially written on the tape (with infinitely many blank squares around it in both directions) and the tape head of the Turing machine is initially positioned over the first (or left-most) symbol of the input string.
At each step in the execution of the Turing machine, the action of the Turing machine is determined by (i) the current state that it is in, and (ii) the symbol written on the square of the tape under the tape head. For each action, the Turing machine:
- chooses which symbol to write on the square of the tape under the tape head. This can be the same symbol that it just read, a different one, or even a blank.
- moves the tape head one square to the Left, one square to the Right, or Stays over the same square.
- determines which internal state it goes to. It can remain in the same state that it is currently in or it can move to a different state.
There is one special state in a Turing machine, a Halt state. As soon as the Turing machine goes to this state, it halts its execution. The output of the Turing machine is the string on the tape when it halts. (The position of the tape head does not matter for the output. And if a Turing machine does not halt, its output is undefined.)
The entire description of a Turing machine can be represented with a transition diagram, like this one:
The transition diagram specifies the tape alphabet, the set of states, and the transition function of a Turing machine. This is all that is required to formally define it.
Definition. A Turing machine is an abstract machine described by the triple
\[M = (Q,\Sigma,\delta)\]where
- \(Q\) is a finite set of internal states;
- \(\Sigma\) is the tape alphabet, a finite set of symbols which includes the blank symbol \(\square\); and
- \(\delta \colon Q \times \Sigma \to (Q \cup \{\mathbf{Halt}\}) \times \Sigma \times \{L,R,S\}\) is the transition function.
A function \(f \colon \sigma^* \to \sigma^*\) that maps strings over the finite alphabet \(\sigma\) to strings over \(\sigma\) is computable if there is a Turing machine \(M\) over a tape alphabet \(\Sigma \supset \sigma\) that for every input string \(s \in \sigma^*\) halts and outputs \(f(s)\).
First Examples
The best way to get acquainted with Turing machines is to look at specific computable functions. We start with some simple functions.
Erase
Consider the function that takes a string of letters in \(\{a,b,c,\ldots,z\}\) and outputs the empty string that we denote by \(\varepsilon\). Formally, the function
\[\mathsf{Erase} \colon \{a,b,c,\ldots,z\}^* \to \{a,b,c,\ldots,z\}^*\]is defined by setting \(\mathsf{Erase}(s) = \varepsilon\) for every string \(s\), where \(\varepsilon\) represents the empty string.
For example, when the input string on the tape is
\[\begin{array}{c|c|c|c|c|c|c|c} \hline \cdots & \phantom{a} & b & a & b & c & \phantom{a} & \cdots \\ \hline \end{array}\]a Turing machine that computes the \(\mathsf{Erase}\) function must halt with the empty tape
\[\begin{array}{c|c|c|c|c|c|c|c} \hline \cdots & \phantom{a} & \phantom{b} & \phantom{a} & \phantom{b} & \phantom{c} & \phantom{a} & \cdots \\ \hline \end{array}\]We can see how a simple Turing machine can do that. Initially, its tape head is on the first symbol — the left-most \(b\) in the example. All it needs to do is overwrite that symbol with a blank and move the tape head to the right. Then it repeats the same process for every symbol that it sees. When it sees a blank on the tape, it will have passed the end of the input string and it halts. This Turing machine is described by the following transition diagram:
Therefore, the \(\mathsf{Erase}\) function is computable.
IsEven?
The task of determining if a number is even or odd can also be represented as a function. For any natural number \(n \in \mathbb{N}\), let us write \(\left< n \right> \in \{0,1\}^*\) to denote its binary encoding. Define
\[\mathsf{IsEven} \colon \{0,1\}^* \to \{0,1\}\]to be the function where for each \(n \in \mathbb{N}\),
\[\mathsf{IsEven}(\left< n \right>) = \begin{cases} 1 & \mbox{if } n \mbox{ is even} \\ 0 & \mbox{otherwise.} \end{cases}\]For example, the input string
\[\begin{array}{c|c|c|c|c|c|c|c|c} \hline \cdots & \phantom{0} & 1 & 0 & 1 & 1 & 0 & \phantom{0} & \cdots \\ \hline \end{array}\]corresponds to the number 22 so a Turing machine that computes \(\mathsf{IsEven}\) halts with the tape containing a single 1:
\[\begin{array}{c|c|c|c|c|c|c|c|c} \hline \cdots & \phantom{0} & \phantom{1} & \phantom{0} & 1 & \phantom{1} & \phantom{0} & \phantom{0} & \cdots \\ \hline \end{array}\]A Turing machine that computes this function is this one:
It is similar to the \(\mathsf{Erase}\) function in that it erases all the symbols on the tape as it goes, but it also uses two states to remember if the last digit read on the tape was a 0 or not. With this information, once it reaches the end of the input string, it can write $0$ or $1$ and then halt, as required.
Church Turing Thesis
The two example functions above are almost trivial, but we can also construct explicit Turing machines to compute many other simple functions as well.
The \(\mathsf{Increment}\) function that takes input \(\left< n \right>\) and outputs \(\left< n + 1 \right>\), for example, can be computed by a Turing machine that implements the standard add-and-carry algorithm. Decrementing can also be computed in a similar way. Then the addition of two numbers can then be accomplished by repeated applications of the increment and decrement operations. And multiplication can be implemented using repeated addition. From there, we can see that many of the functions that represent standard arithmetic operations are computable.
And Turing machines can also compute simple functions on inputs that represent other types of objects as well. A simple example of a computable functino on strings, for example, is the \(\textsf{Copy}\) function that on input \(x\) returns the string \(xx\). Other Turing machines can be constructed to show that inserting a symbol at the beginning, the middle, or the end of a string is computable; that reversing a string is computable; that determining if a string is a palindrome or not is computable, etc.
In fact, Turing machines appear to be able to compute every function that can be computed with a standard algorithm. The Church-Turing thesis asserts that this is no accident:
Church-Turing thesis. Every function that can be computed by algorithms in any reasonable model of computation can also be computed by a Turing machine.
At this point, we might ask if we can go even further: is it possible that every function which we can define is computable? This is the question we will answer in the next lecture.