A Turing machine is a mathematical model of a mechanical machine. At its roots, the Turing machine uses a read/write head to manipulate symbols on a tape. It was invented by the computer scientist Alan Turing in 1936. Interestingly, according to the Church-Turing thesis this simple machine can do everything any other computer can do; including our contemporary computers. Though these machines are not a practical or efficient means to calculate something in the real world, they can be used to reason about computability and other properties of computer programs.

A portrait photograph of Alan Turing. The image is in grayscale. Alan is looking ahead and the photograph is taken just off-angle from head-on. — Alan Turing

Definition

There are various different, but equivalent, Turing machine definitions. A one-tape Turing machine $M$ can be defined as a 6-tuple

M = \left\langle Q, \Sigma, \Gamma, \delta, q_0, F \right\rangle

with:

$Q$ : Set of states of the machine $\Sigma$ : Input alphabet of the machine $\Gamma$ : Tape alphabet (including the blank symbol $B$ , and all symbols in the input alphabet are also in the tape alphabet, $\Sigma \subset \Gamma$ ) $\delta$ : Transition function $\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \left\lbrace L, R \right\rbrace$ ; i.e. given a state and a symbol, the transition function will tell what the new state is, which symbol should be written and whether the head should move left or right, e.g.: $\delta(q_0, B) = \left[ q_1, B, R \right]$ $q_0$ : Initial state, $q_0 \in Q$ $F$ : Set of accepting states, $F \subseteq Q$

The input of the Turing machine is written on the initial tape configuration. We assume that initially the first symbol on the tape is always the blank symbol $B$ , and that the following symbols are the input. We also assume that the input is followed by an infinite sequence of blank symbols (i.e., the tape is infinite).

For example, if the input is “1011”, the tape would be:

Position  0  1  2  3  4  5  6  ...
Symbol    B  1  0  1  1  B  B  ...

The Turing machine will start its computation in the initial state $q_0$ with the head at tape position 0. It will follow the transitions in the transition function, and halts when there are no more transitions it is able to take from the current head position. The input is accepted if the halting state is an accepting state. The output is the tape content after the machine has halted, but note that it is possible for machines to never halt for certain inputs.

An Example

We can represent Turing machines graphically. Let’s look at an example machine:

A schematic diagram of a Turing machine. It has three circles representing states, labeled: q0, q1 and q2. There is an unlabeled arrow going into q0 indicating it is the starting state. State q2 is circled twice, indicating it is an accepting state. There are five labeled arrows. There is an arrow from q0 to q1 labeled B/BR. There is an arrow from q1 to itself labeled 0/1R. There is an arrow from q1 to q2 labeled 1/0R. There is an arrow from q2 to q1 labeled 0/1R. There is an arrow from q2 to itself labeled 1/0R. — An example Turing machine with three states, of which q2 is an accepting state. The arrow labels x/yd model the transitions from one state to the other, where x is the symbol that is read, y is the symbol it is replaced with, and d is the direction the head moves to. The initial state is indicated by the arrow pointing from nothing to q0.

This machine describes the machine $M$ with:

\begin{aligned} Q &= \left\lbrace q_0, q_1, q_2 \right\rbrace \\ \Sigma &= \left\lbrace 0, 1 \right\rbrace \\ \Gamma &= \left\lbrace 0, 1, B \right\rbrace \\ F &= \left\lbrace q_2 \right\rbrace \\ \delta(q_0, B) &= \left[ q_1, B, R \right] \\ \delta(q_1, 0) &= \left[ q_1, 1, R \right] \\ \delta(q_1, 1) &= \left[ q_2, 0, R \right] \\ \delta(q_2, 0) &= \left[ q_1, 1, R \right] \\ \delta(q_2, 1) &= \left[ q_2, 0, R \right] \end{aligned}

and initial state $q_0$ .

If we run this machine with input “1011”, we compute $M(1011)$ . We can follow the computation by evaluating what the machine does at each step:

Step 1
Tape: B1011BB…
State: $q_0$
Symbol: B
Transition: $\delta(q_0, B) = \left[ q_1, B, R \right]$

Step 2
Tape: B1011BB…
State: $q_1$
Symbol: 1
Transition: $\delta(q_1, 1) = \left[ q_2, 0, R \right]$

Step 3
Tape: B0011BB…
State: $q_2$
Symbol: 0
Transition: $\delta(q_2, 0) = \left[ q_1, 1, R \right]$

Step 4
Tape: B0111BB…
State: $q_1$
Symbol: 1
Transition: $\delta(q_1, 1) = \left[ q_2, 0, R \right]$

Step 5
Tape: B0101BB…
State: $q_2$
Symbol: 1
Transition: $\delta(q_2, 1) = \left[ q_2, 0, R \right]$

Step 6
Tape: B0100BB…
State: $q_2$
Symbol: B
Transition: halt

The input is accepted as the machine stops in $q_2 \in F$ . The output is the input with 0s and 1s flipped: “0100”. By analyzing the machine, we can easily see that it accepts any input that ends with a “1”, and that the output is always the input with 0s and 1s flipped.

Encoding

Sometimes we want computer programs to perform computations with as input other computer programs. For example, a compiler takes source code and turns it into a program, a virus scanner can look at programs and indicate whether it believes they are viruses or not, and an interpreter takes source code and directly executes the program that is described. To be able to look at Turing machines with Turing machines, we require a means to encode such machines.

There are many different encodings possible. One such encoding is the following, where we encode Turing machines as strings of 0s and 1s. Given a machine $M$ , and by ignoring accepting states, the encoding of $M$ is $R(M)$ :

R(M) = 000\underbrace{en_\text{tr}(\delta_1)00en_\text{tr}(\delta_2)...00en_\text{tr}(\delta_n)}_{\text{Encode each transition}}000

with for a transition $\delta_k$ :

\begin{aligned} \delta_k(q_i, x) &= \left[ q_j, y, d \right] \\ en_\text{tr}(\delta_k) &= en_\text{st}(q_i)0en_\text{sym}(x)0en_\text{st}(q_j)0en_\text{sym}(y)0en_\text{dir}(d) \end{aligned}

with:

\begin{aligned} en_\text{st}(q_i) &= \underbrace{11...1}_{\text{i+1 1s}} = 1^{i+1} \\ en_\text{sym}(x) &= \begin{cases} 1 & \text{if } x = 0 \\ 11 & \text{if } x = 1 \\ 111 & \text{if } x = B \end{cases} \\ en_\text{dir}(d) &= \begin{cases} 1 & \text{if } d = L \\ 11 & \text{if } d = R \end{cases} \end{aligned}

Thus, the encoding of a Turing machine is three 0s followed by the encoding of the transitions (separated by two 0s), and ends with three 0s. The example Turing machine above would be encoded to (transitions are separated by spaces for clarity):

000 101110110111011 00 1101011011011 00 11011011101011 00 11101011011011 00 111011011101011 000

Languages

A formal language is not the same as a natural language (such as English). A formal language is a set of strings made from symbols, and certain rules may apply as to which strings are in the language. Turing machines can recognize certain types of formal languages. The example machine above recognizes the language $L(M) = \left\lbrace w \in \left\lbrace 0, 1 \right\rbrace^* | w \text{ ends with } 1 \right\rbrace$ ; that is, it recognizes the language of all strings of 1s and 0s that end with a 1. Note that in recognizing languages, the output of machines is irrelevant. We only need to know whether the input is accepted or not.

There are two types of languages related to Turing machines, recursive languages and recursively enumerable languages. A recursive language is a language for which there exists a Turing machine that will accept any string that is in the language, and rejects any other string. It is important that this machine halts for every possible input. On the other hand, a recursively enumerable language is one for which we can construct a Turing machine that will enumerate all strings in the language, meaning that it will produce output:

B  w1  B  w2  B  w3  B  w4  B  ...

with $w_i$ valid strings in the language. For infinite languages this enumeration operation will obviously never halt, but any given string will be reached eventually. Note that this means there does not need to exist a Turing machine that will tell you for all possible inputs whether it is or is not in the language. One is able to construct a machine that will recognize and halt for each valid string, but you cannot guarantee that the machine will halt for strings that are not in the language. One such machine can be constructed from the enumeration machine: enumerate until you find the input string, then halt and accept. Clearly, if the input string is not a valid string and the language is infinite, this machine will never halt.

The set of recursive languages is a subset of the recursively enumerable languages. Given a machine $M$ that halts for any input and accepts precisely the words of language $L$ , we can construct a machine that enumerates language $L$ . The enumerating Turing machine $M'$ for language $L$ generates all possible strings $w_i$ and places them on the output if $w_i$ is accepted by $M$ .

Halting Problem

Given an input and a description of a Turing machine (or any computer program), the halting problem is the problem of determining whether the computation will halt eventually or will run forever. Using his Turing machines, Alan Turing proved that there cannot exist a general algorithm that solves the halting problem for all pairs of computer programs and inputs; the halting problem is undecidable.

We will now prove that the halting problem is undecidable. If the halting problem would be decidable, we could make a Turing machine $H$ that, given an encoding of a Turing machine $M$ and an input $w$ for that machine, would give as output 1 if $M(w)$ halts, and 0 if it does not. Using $H$ , we can make a machine $D$ that takes as input the code for a Turing machine $M$ and asks $H$ whether that machine halts when it looks at input $R(M)$ ; i.e., $D$ asks $H$ whether $M(R(M))$ halts. Then, we construct $D$ such that it halts precisely when $M(R(M))$ does not.

D(R(M)) \text{ halts} \iff M(R(M)) \text{ does not halt}

Now, instead of making $D$ look at an arbitrary machine, we make $D$ look at itself: we compute $D(R(D))$ . Using our definition of $D$ , we see that $D(R(D))$ halts precisely when its input machine on its encoding, $D(R(D))$ , does not.

D(R(D)) \text{ halts} \iff D(R(D)) \text{ does not halt}

However, this is a contradiction. As such, our initial assumption that the halting problem is decidable must be invalid; the halting problem is undecidable.

Gödel’s Incompleteness Theorem

Gödel’s first incompleteness theorem states that in a consistent logic system, you will not be able to prove everything that is true. A consistent logic system is one which does not contain contradictions. The first incompleteness theorem follows directly from the halting problem. To prove this, we start by assuming that we can prove all things that are true. Take two things: one being that a computer program will halt for a given input, and the other being that that computer program will not halt for that input. Given our assumption, we would be able to prove that one of these is true, and thus we would be able to decide the halting problem. However, we know that the halting problem is undecidable, so this is a contradiction. It follows that we cannot prove all things that are true, which proves Gödel’s first incompleteness theorem.