Turing machines play a fundamental role in the algorithms and computational theory. The concept of Turing machine was invented by Alan Turing in 1937. This simple hypothetical device is able to compute all the functions which are algorithmically computable. Before we deal with the Turing machine as a universal tool for describing algorithms, we introduce the Turing machine as a universal language definition device.
The basic concept is that the Turing machine manipulates a string on a two-way infinite tape according to transition rules, and decides whether or not the input string belongs to a language accepted by the Turing machine. The tape contains an infinite number of cells, and each cell contains one letter. At the beginning, the tape contains the input string, and the rest of the cells contain a special tape symbol called a blank symbol. There is a head, which can read and write the content of the current cell of the tape, and can move both to the left and to the right. At the beginning, the head is over the first letter of the input string. The Turing machine also has its own inner state, which can be changed in each step. At the beginning, the inner state of the Turing machine is the initial state. The transition rules are the "program" of the Turing machine.
In each step the machine reads the letter contained by the current cell of the tape, and also reads its own inner state, then writes a letter into the current cell, changes its inner state and moves the head to the left or to the right, or stays in the same position. Sometimes, it does not change its inner state, and sometimes it does not change the content of the current cell. The operations of the Turing machine are based on the transition rules.
Let us see the formal definition and the detailed description.
Definition 33. The (nondeterministic) Turing machine (TM) is the following 7-tuple:
TM = (Q, T, V, q0, #, δ, F)
where
Q is the finite nonempty set of the states,
T is the set of the input letters, (finite nonempty alphabet), T ⊆ V,
V is the set of the tape symbols, (finite nonempty alphabet),
q0 is the initial state, q0 ∈ Q,
# is the blank symbol, # ∈ V,
δ is the transition function having a form Q × V → 2Q×V×{Left, Right, Stay}, and
F is the set of the final states, F ⊆ Q.
We have a description of the parts of our device, and now we have to describe its operation. In each step, the Turing machine has its configuration (u,q,av), where q ∈ Q is the current state, a ∈ V is the letter contained by the current cell, and u, v ∈ V* are the words before and after the current letter, respectively. The first letter of the word u and the last letter of the word v cannot be the blank symbol, and the word uav is the "important" part of the tape, the rest of the tape contains only blank symbols. At the beginning, the Turing machine has its initial configuration: (λ, q0, av), where av is the whole input word. In each step, the Turing machine changes its configuration according to the transition function. There are three possibilities, depending on the movement part of the applied rule.
The simplest case is when the applied transition rule has a form (q2, a2, Stay) ∈ δ (q1, a1). In this case, we just change the state and the symbol contained by the current cell of the tape according to the current rule. Formally, we say the TM can change its configuration from (u, q1, a1v) to (u, q2, a2v) in one step, if it has a transition rule (q2, a2, Stay) ∈ δ (q1, a1), where q1, q2 ∈ Q, a1, a2 ∈ V, and u, v ∈ V*.
Mark: (u, q1, a1v) ⊦TM (u, q2, a2v).
The next possibility is when the applied transition rule has a form (q2, a2, Right) ∈ δ (q1, a1). In this case, we change the state and the symbol contained by the current cell of the tape according to the current rule, and move the head to the right. Formally, we say the TM can change its configuration from (u, q1, a1v) to (ua2, q2, v) in one step, if it has a transition rule (q2, a2, Right) ∈ δ (q1, a1), where q1, q2 ∈ Q, a1, a2 ∈ V, and u, v ∈ V*.
It is denoted by (u, q1, a1v) ⊦TM (ua2, q2, v).
Here, we have a special case, namely, if a2 = # and u = λ, then (u, q1, a1v) ⊦TM (λ, q2, v).
The last possibility is when the applied transition rule has a form (q2, a2, Left) ∈ δ(q1, a1). In this case, we change the state and the symbol contained by the current cell of the tape according to the current rule, and move the head to the left. To formalize this case, we have to write the word u in a form u = wb, where b is the last letter of the word u. We say that the TM can change its configuration from (wb, q1, a1v) to (w, q2, ba2v) in one step, if it has a transition rule (q2, a2, Left) ∈ δ (q1, a1), where q1, q2 ∈ Q, a1, a2, b ∈ V, and w, v ∈ V*.
It is denoted by (wb, q1, a1v) ⊦TM (w, q2, ba2v).
Here, we also have a special case, namely, if a2 = # and v = λ, then (wb, q1, a1v) ⊦TM (w, q2, b).
Now, let X and Y be configurations of the same Turing machine. Then, we say that the Turing machine can change its configuration from X to Y in finite number of steps, if X = Y, or there are configurations C0, C1, ..., Cn such that C0 = X, Cn = Y, and Ci ⊦TM Ci+1 holds for each integer 0 ≤ i < n.
It is denoted by X ⊦*TM Y.
A configuration is called a final configuration, if the Turing machine is in a final state. Now, we can define the language accepted by the Turing machine. The input word is accepted, if the Turing machine can change its configuration from the initial configuration to a final configuration in finite number of steps.
L(TM) = {p∣p ∈ T*, (λ, q0, p) ⊦*TM (u, qf, av), qf ∈ F, a ∈ V, u, v ∈ V*}.
Example 57. Let the language L be the language of the palindromes over the alphabet {a, b}. (Palindromes are words that reads the same backward or forward.) This example shows the description of a Turing machine TM, which accepts the language L.
TM = ({q0,q1,q2,q3,q4,q5,qf}, {a,b}, {a,b,#}, q0,#,δ, {qf}) δ(q0,#) = {(qf,#,Stay)}, δ(q0,a) = {(q1,#,Right)}, δ(q0,b) = {(q2,#,Right}, δ(q1,a) = {(q1,a,Right)}, δ(q1,b) = {(q1,b,Right)}, δ(q1,#) = {(q3,#,Left)}, δ(q3,a) = {(q5,#,Left)}, δ(q3,#) = {(qf,#,Stay)}, δ(q2,a) = {(q2,a,Right)}, δ(q2,b) = {(q2,b,Right)}, δ(q2,#) = {(q4,#,Left)}, δ(q4,#) = {(qf,#,Stay)}, δ(q4,b) = {(q5,#,Left)}, δ(q5,a) = {(q5,a,Left)}, δ(q5,b) = {(q5,b,Left)}, δ(q5,#) = {(q0,#,Right)}.
Exercise 79. Create a Turing machine, which accepts words over the alphabet {a,b} containing the same number of a's and b's.
Exercise 80. Create a Turing machine, which accepts words over the alphabet {a,b} if they are a repetition of another word.
Exercise 81. Create a Turing machine, which accepts binary numbers greater than 20.
Our final note is that, although it is a simple construction, Turing machines can accept any language from the recursively enumerable language class. This statement is formulated in the following theorem.
Theorem 43. A language L is recursively enumerable, if and only if there exists a Turing machine TM such that L = L(TM).
There are several equivalent definitions for the Turing machine. In this subsection we are going to introduce some of them. Our first definition is the deterministic Turing machine, which has the same language definition power as the nondeterministic Turing machine. A Turing machine is called deterministic, if from each configuration it can reach at most one other configuration in one step. The formal definition is the following:
Definition 34 The Turing machine TMd = (Q, T, V, q0, #, δ, F) is deterministic, if the transition function δ(q,a) has at most one element for each pair (q,a), where q ∈ Q and a ∈ V.
In other words, the Turing machine TMd = (Q, T, V, q0, #, δ, F) is deterministic, if the form of the transition function δ is Q × V → Q × V × {Left, Right, Stay}.
Theorem 44. For each Turing machine TM there exists a deterministic Turing machine TMd such that L(TM) = L(TMd).
Now, we are going to introduce the multitape Turing machine, which looks like a more powerful tool compared to the original Turing machine, but in reality it has the same language definition power. In this case, we have more than one tape, and we work on each tape in each step. At the beginning, the input word is written on the first tape, and the other tapes are empty. (Contains blank symbols in each position.) The multitape Turing machine is in initial state, and the head is over the first letter of the first tape. In each step the multitape Turing machine reads its own state and the symbols from the cells of each tape, then changes its state; it writes symbols into the current cell of each tape and moves the head to the left or to the right, or stays in a same position over each tape separately. Observing the formal definition, its only difference compared to the deterministic Turing machine is that it has more tapes, and as a result, it has a different transition function.
Definition 35. The multitape Turing machine is the following octuple TMm = (k, Q, T, V, q0, #, δ, F), where Q, T, V, q0, # and F are the same as before, the integer k ≥ 0 is the number of the tapes, and the form of the transition function δ is Q × Vk → Q × (V × {Left, Right, Stay})k.
As we have noted before, multitape Turing machines accept recursively enumerable languages as well.
Theorem 45. For each multitape Turing machine TMm there exists (a one-tape) Turing machine TM such that L(TM) = L(TMm).
The reason for using the multitape Turing machine or the deterministic Turing machine instead of the original Turing machine is very simple. Sometimes it is more comfortable to use these alternative Turing machines for calculating or proving theorems.
For the same purpose, sometimes we use a Turing machine which has one tape, and this tape is infinite in one direction, and the other direction is "blocked". This version has a special tape symbol in the first cell, and when the Turing machine reads this symbol, the head moves to the right and does not change this special symbol. There is yet another possibility, when the Turing machine must not stay in the same position, in each step the head must move to the right or to the left. Sometimes we use only one final state, and sometimes we use a rejecting state as well, but all of these versions are equivalent to each other. Each of the Turing machine described above accepts recursively enumerable languages, and each recursively enumerable language can be accepted by each type of the above mention Turing machines.