An Overview of Turing Machines

The famous mathematician Alan Turing introduced the abstract concept of a Turing machine as a part of his research on a problem that was introduced in 1928 by David Hilbert called Entscheidungsproblem. The importance of Turing machines arises because they're one of the first theoretical models for computers and, consequently, a number of theories and ideas in the computer science field were based on this concept. In this post, I'm going to walk you through Turing Machines' concept.

There are multiple versions of Turing machines, but the most popular and intuitive one is the standard Turing machine (STM). Throughout this post, the STM will be used.

Informal Definition
Formal Definition
Transitions
Language acceptors VS. transducers
Example

Informal Definition

Turing machine has a tape which is infinite from both sides of the input. The following picture visualizes the tape of the input aabbcc:

Cells on each side of the input are empty (i.e. blanks) and denoted by the symbol □.

There's a scanner that scans the cell content and performs the next action based on the scanned input. The next action can be writing in the current cell and then moving left/right. In the initial configuration of the Turing machine, the scanner is set to the leftmost character of the input as the following picture shows:

A Turing machine accepts strings that halt in a final state which merely depends on the scanner (which has a kind of a Finite automaton). Therefore, we can conclude that the tape contents are irrelevant to the acceptance of strings.

A Turing machine rejects strings that halt in a non-final states or don't halt at all. In the latter case, the Turing machine runs into an infinite loop because of the input string.

Formal Definition

The formal definition is easier to understand when it's read simultaneously with a real example. If you feel that you are unable to digest the definition, take a look at the example provided in Example section.

A Turing machine M is defined by
M = (Q,Σ,Γ,δ,q₀, ,F) where
Q is the set of internal states,
Σ is the input alphabet
Γ is the finite set of symbols called the tape alphabet,
δ is the transition function,
□ ∈ Γ is a special symbol called the blank,
q₀ ∈ Q is the initial state,
F ⊆ Q is the set of final states.

In the definition of a Turing machine, we assume that Σ ⊆ Γ – {□}, that is, that the input alphabet is a subset of the tape alphabet, not including the blank. Blanks are ruled out as input for reasons that will become apparent shortly. The transition function δ is defined as δ : Q × Γ → Q × Γ × {L,R}.

Transitions

δ(q, a) = (q₀, b,R) means that from state q, if you see a on tape, go to state q₀, write b on tape, and move one square to the right on the tape.

δ(q, a) = (q₀, b, L) means same as above, except move left on the tape.

What if δ(q, a) is undefined ? (i.e. δ(q, a) = Φ, there is no move corresponds to the pair of (q,a)). Simply, we say that the Turing machine halts. As discussed earlier, if the machine halts in a final state, it accepts the input string. Otherwise, it rejects the input string.

Language acceptors VS. transducers

A Turing machine that accepts a specific language, similar to finite automata and PDAs, is called language acceptor.

A Turing machine that take an input string and transforms it to an output is called transducers.

Example

Let's take the language L={aⁿbⁿcⁿ | n ≥ 0} to help us understand what the concept of Turing machines is.

Before start trying to tackle this language and design a Turing machine for it, we should understand what string it contains. This language contains all ordered strings such that a's at the beginning of the string, b's at the middle and c's at the end where the number of a's, b's and c's match.

Our Turing machine should match one a with one b with one c and keep looping until the entire string is matched to accept the string. Here's a visualized of this procedure on the string aabbcc:

In the first iteration, the leftmost "a" will be converted to "A" symbol (can be any other symbol). Then the scanner will skip all small a's and convert the leftmost "b" to "B" symbol. Then the scanner will skip all small b's and convert the leftmost "c" to "C" symbol. After that, the scanner will go left skipping all "C" symbols, b's, "B" symbols and a's until it reaches an "A" symbol and it will go right to start the matching process again. At this point, the scanner will be on the left most "a" (note it's a small "a") and it'll proceeds as the first iteration with a minor difference is that the Turing machine will skip any "B" and "C" symbols. After the scanner finishes matching and goes back to the rightmost "A", it will move one cell to the right which is a cell that contains "B". When the scanner faces "B" symbol after moving on cell right, it's a sign that the string is matched. Then it will move to the right skipping all "B" and "C" symbols to verify that the b's and c's are all matched. The Turing machine will halt in a final state if after skipping all "B" and "C" symbols, the scanner reached a blank.

Here's the Turing machine design that accepts the Language L: