Turing Machines

A Turing machine is an abstract computational model that performs computations by reading and writing to an infinite tape. Turing machines provide a powerful computational model for solving problems in computer science and testing the limits of computation — are there problems that we simply cannot solve? Turing machines are similar to finite automata/finite state machines but have the advantage of unlimited memory. They are capable of simulating common computers; a problem that a common computer can solve (given enough memory) will also be solvable using a Turing machine, and vice versa. Turing machines were invented by the esteemed computer scientist Alan Turing in 1936.

Here is a Turing machine that checks if an input string is a palindrome.

The tape head moves along the tape reading and writing symbols as directed by the Turing machine's programming.

A Turing machine consists of an infinite tape (as the memory), a tape head (a pointer to the currently inspected cell of memory), and a state transition table (to govern the behavior of the machine). Each cell of the tape can have one of a predetermined finite set of symbols, one of which is the blank symbol.

A Turing machine, like an algorithm, executes on an input string of bits. At the beginning, the input string is written on the tape, the tape head points to the first cell of the string, and all other cells are blank.

During operation, the tape head is in a certain state. Every step, it consults the table (the set of transition functions), based on only the state it's in and the symbol underneath the head, to obtain its next choice: either halt (end the operation), or resume by writing a symbol to the current cell, changing its state, and moving to the left or the right. This way, A Turing machine can simulate the fact that a program is made of many lines and thus it depends on what line a program is executing, and it can also simulate the fact that a program can react differently with different data in memory.

A Turing machine can thus either halt at some point or run forever. If it halts, the contents of the tape are the output.

There are many Turing machine simulators online, such as this simulator that created the example above.

As shown in the animation above, a Turing machine consists of a tape that is initialized with a string of symbols. The machine has a head that reads and writes symbols as it moves along the tape.

When the tape reads any particular symbol, it decides what to do (what to write to the tape at that point and then which direction to move in next) depending on the set of transition functions associated with the machine. A transition function is essentially a specific instruction line in a Turing machine’s program. You can think of the set of transition functions as the complete program that specifies what the Turing machine should do on any valid input it receives.

In practice, a transition function takes the following form (see below for a formalized definition).

• What state I am in right now

• What symbol I just read

• What symbol I should write

• What state I should change to next

• Which direction I should move in next

The order of these inputs can vary depending on which Turing machine simulator you are using to run your machine, but all of this information will be included.

A state can be thought of as a subset of rules. For example, if a Turing machine has two states, when the head reads an “A” symbol in state $1$, the machine might do one thing, and if the head reads an “A” symbol in state $2$, it can do a different thing.

Transition functions are often represented in a table form. The table below describes a simple Turing machine that takes a string of $1$’s as input and doubles it. So “11” becomes “1111” and so forth. In the specification below, there are three states: state 0,1, and 2. Halt is a special state you can use to indicate that your program has concluded. There are 2 symbols: 1 and A. There are three options for which direction to move: left, right, and stay (indicated by *).

Here, the symbol “A” is used to indicate a “1” that we have already seen, and when we read a “1” we write an “A”. This is so we don’t double count symbols. Once we’ve changed all of the 1’s to A’s, all of the symbols on the tape will be A’s. Then, change all of the A’s to 1’s and the original string has been doubled.

Let’s go through this string-doubling Turing machine (described by the table above) step by step on the input “111” (though this machine will double any string of 1’s).

The code below the tape shows the transition functions. The next step to be taken is highlighted with blue, and the previous step is highlighted in orange.

(note in the simulation above, left is denoted by a lower-case L, and right is denoted by a lower-case R.)

A Turing machine is formally defined as a 7-tuple $\langle Q, q_0, F, \Gamma, b, \Sigma, \delta \rangle$, where

• $Q$ is a finite, non-empty set of states
• $q_0 \in Q$ is the initial state
• $F \subset Q$ is the set of accepting states
• $\Gamma$ is a finite, non-empty set of tape symbols
• $b \in \Gamma$ is the blank symbol
• $\Sigma \subset \Gamma \setminus \{b\}$ is a set of input symbols
• $\delta : (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R\}$ is the transition function, which is a partial function

A Turing machine's operation is a sequence $(\langle q'_s, h_s, (t_{s,p})_{p=-\infty}^\infty \rangle)_{s=0}^\infty$, where

• $q_s$ is the state of the tape head in the $s$-th step
• $h_s$ is the position of the tape head in the $s$-th step
• $t_{s,p}$ is the content of the tape in the $s$-th step and $p$-th position

such that

• $q'_0 = q_0$
• $h_0 = 0$
• If the input string is $(x_1, \ldots, x_n) \in \Sigma^n$, then $t_{0,p} = x_{p+1}$ for $0 \le p \le n-1$ and $t_{0,p} = b$ otherwise
• If $\delta(q_s, t_{s, h_s}) = (q, t, d)$, then:
  • $q_{s+1} = q$
  • $h_{s+1} = h_s - 1$ if $d = L$, and $h_{s+1} = h_s + 1$ if $d = R$
  • $t_{s+1, p} = t$ if $p = h_s$, and $t_{s+1, p} = t_{s, p}$ otherwise
• Otherwise, if $q_s \in F$ or $\delta(q_s, t_{s, h_s})$ is not defined, then the machine halts; the rest of the sequence is not defined, and $s$ is the number of steps taken by the machine.

The transition functions define the rules, or the program, for the Turing machine. Transition functions are often represented in tables. Transition functions encode what the Turing machine should do upon reading each possible inputs (so all the symbols in $\Gamma$). Essentially, a transition function is of the following form: "If you read symbol $X$, and you are currently in state $S_a$, write symbol $Y$, move in this direction, and switch to state $S_b$." Where $X$ and $Y$ represent some symbol in $\Gamma$ and $S_a$ and $S_b$ are states in $Q.$ An instruction might say "write the same symbol you read" or "stay in the same state" — it is all up to the programmer defining the transition functions. The programmer must write out an appropriate​ set of instructions to accomplish the task at hand.

Turing machines can recognize and decide different kinds of problems and languages. Languages describe problems. For example, there is a language of all strings made up entirely of 1's — some members of this language would be "1", "111111", "111111111", etc. One could make a Turing machine to compute these strings. For example, write a program that just makes the Turing machine write a 1 each time it moves to the right and have it so the machine always moves to the right.

Recognizability

A language is recognizable if a Turing machine accepts when an input string is in the language, and either rejects or loops forever when an input string is not in the language. In other words, if a language is recognizable there are strings not in the language for which the Turing machine may not halt.

Decidability

A language is decidable if a Turing machine accepts strings that are in the language and rejects strings that are not in the language. In other words, the Turing machine will halt on all inputs. All decidable languages are recognizable, but not all recognizable languages are decidable. The halting problem is an important example of a recognizable problem that is undecidable.

The Church-Turing thesis claims that any computable problem can be computed by a Turing machine. This means that a computer more powerful than a Turing machine is not necessary to solve computable problems. The idea of Turing completeness is closely related to this. A system is Turing complete if it can compute every Turing computable function. A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete.

To prove that something is Turing complete, it is sufficient to show that it can simulate some other Turing complete system. Usually, it is easiest to show that a system can simulate a universal Turing machine. A universal Turing machine is a Turing machine that can simulate any other Turing machine.

• Finite State Machines

• The Halting Problem

• universal Turing machine

• Church-Turing thesis

• Multi-tape Turing Machines

• Nondeterministic Turing Machines