Turing machine

The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or 'mechanical procedure'.
As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation.
The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as the Church-Turing thesis.

The concept of the Turing machine is based on the idea of a person executing a well-defined procedure by changing the contents of an infinite number of ordered paper sheets that can contain one of a finite set of symbols. The person needs to remember one of a finite set of states and the procedure is formulated in very basic steps in the form of "If your state is 42 and the symbol you see is a '0' then replace this with a '1', remember the state 17, and go to the following sheet."

Turing machines shouldn't be confused with the Turing test,
Turing's attempt to capture the notion of artificial intelligence.

A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine or simply a universal machine as Turing described it in 1947:

It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine.

Definition

Informal description

A Turing machine is a pushdown automaton made more powerful by relaxing the last-in-first-out requirement of its stack. (Interestingly, a seemingly minor relaxation enables the Turing machine to perform such a wide variety of computations that it can serve as a model for the computational capabilities of all modern computer software.)

More precisely, a Turing machine consists of:

A tape which is divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendible to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written to before are assumed to be filled with the blank symbol.

A head that can read and write symbols on the tape and move left and right.

A state register that stores the state of the Turing machine. The number of different states is always finite and there is one special start state with which the state register is initialized.

An action table (or transition function) that tells the machine what symbol to write, how to move the head ('L' for one step left, and 'R' for one step right) and what its new state will be, given the symbol it has just read on the tape and the state it is currently in. If there is no entry in the table for the current combination of symbol and state then the machine will halt.
Note that every part of the machine is finite, but it is the potentially unlimited amount of tape that gives it an unbounded amount of storage space.

Formal definition

= One-tape Turing machine =

More formally, a (one-tape) Turing machine is usually defined as a 6-tuple , where

is a finite set of states
is a finite set of the tape alphabet
is the initial state
is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
is the set of final or accepting states
is a partial function called the transition function, where L is left shift, R is right shift.

Definitions in the literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always done in such a way that the resulting machine has the same computational power. For example, changing the set to , where S would allow the machine to stay on the same tape cell instead of moving left or right, does not increase the machine's computational power.

= k-tape Turing machine =

A k-tape Turing machine can similarly be described as a 6-tuple , where

is a finite set of states
is a finite set of the tape alphabet
is the initial state
is the blank symbol
is the set of final or accepting states
is a partial function called the transition function, where L is left shift, R is right shift, S is no shift.

Note that a k-tape Turing Machine is no more powerful than a standard Turing Machine.

Example

The following Turing machine has an alphabet {'0', '1'}, with 0 being the blank symbol. It expects a series of 1's on the tape, with the head initially on the leftmost 1, and doubles the 1's with a 0 in between, i.e., "111" becomes "1110111".
The set of states is {s1, s2, s3, s4, s5} and the start state is s1.
The action table is as follows.

Old Read Wr. New Old Read Wr. New St. Sym. Sym. Mv. St. St. Sym. Sym. Mv. St. - - - - - - - - - - - - - - - - - - - - - - - - s1 1 -> 0 R s2 s4 1 -> 1 L s4 s2 1 -> 1 R s2 s4 0 -> 0 L s5 s2 0 -> 0 R s3 s5 1 -> 1 L s5 s3 0 -> 1 L s4 s5 0 -> 1 R s1 s3 1 -> 1 R s3 A computation of this Turing machine might for example be:
(the position of the head is indicated by displaying the cell in bold face)

Step State Tape Step State Tape - - - - - - - - - - - - - - - - - 1 s1 11 9 s2 1001 2 s2 01 10 s3 1001 3 s2 010 11 s3 10010 4 s3 0100 12 s4 10011 5 s4 0101 13 s4 10011 6 s5 0101 14 s5 10011 7 s5 0101 15 s1 11011 8 s1 1101 -- halt -- The behavior of this machine can be described as a loop:
it starts out in s1, replaces the first 1 with a 0, then uses s2 to move to the right, skipping over 1's and the first 0 encountered. S3 then skips over the next sequence of 1's (initially there are none) and replaces the first 0 it finds with a 1. S4 moves back to the left, skipping over 1's until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1's until it finds the 0 that was originally written by s1.
It replaces that 0 with a 1, moves one position to the right and enters s1 again for another round of the loop.
This continues until s1 finds a 0 (this is the 0 right in the middle between the two strings of 1's) at which time the machine halts.

Deterministic and non-deterministic Turing machines

If the action table has at most one entry for each combination of symbol and state then the machine is a deterministic Turing machine (DTM). If the action table contains multiple entries for a combination of symbol and state then the machine is a non-deterministic Turing machine (NDTM or NTM).

Universal Turing machines

Every Turing machine computes a certain fixed partial computable function from the input strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, as Alan Turing already described, we can encode the action table of any Turing machine in a string. Thus we might try to construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape that the encoded Turing machine would have computed.
As Turing showed, such a Turing machine is indeed possible and since it is able to simulate any other Turing machine it is called a universal Turing machine.

With this encoding of action tables as strings, it becomes possible in principle
for Turing machines to answer questions about the behavior of other Turing machines.
Most of these questions, however, are undecidable, meaning that the function in question cannot be calculated by any Turing machine.
For instance, the problem of determining whether a particular Turing machine will halt on a particular input, or on all inputs, known as the Halting problem, was shown to be undecidable in Turing's original paper.
Rice's theorem shows that any nontrivial question about the behavior or output of a Turing machine is undecidable.

If we broaden the definition to include any Turing machine that simulates some Turing-complete computational model, not just Turing machines that directly simulate other Turing machines, a universal Turing machine can be fairly simple, using just a few states and a few symbols. For example, only 2 states are needed, since a 2×18 (meaning 2 states, 18 symbols) universal Turing machine is known.
A complete list of the smallest known universal Turing machines is: 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2.
These simulate a computational model called tag systems.

A universal Turing machine is Turing-complete.
It can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language.
According to the Church-Turing thesis, the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.

Comparison with real machines

It's often said that Turing machines, unlike simpler automata, are as powerful as real machines, and are able to execute any operation that a real program can. What is missed in this statement is that almost any particular program running on a particular machine and given a finite amount of input is in fact nothing but a deterministic finite automaton, since the machine it runs on can only be in finitely many configurations. Turing machines would actually only be equivalent to a machine that had an infinite amount of storage space. We might ask, then, why Turing machines are useful models of real computers. There are a number of ways to answer this:

The difference lies only with the ability of a Turing machine to manipulate unbounded amout of data. However, an actual running of a Turing machine that manipulates unbounded data, takes unbounded time to do so.

Real machines are much more complex than a Turing machine. For example, a Turing machine describing an algorithm may have a few hundred states, while the equivalent DFA on a given real machine has quadrillions.

Turing machines describe algorithms independent of how much memory they utilize. There is a maximum to the amount of memory that any machine which we know of has, but this limit can rise arbitrarily in time. Turing machines allow us to make statements about algorithms which will (theoretically) hold forever, regardless of advances in conventional computing machine architecture.

Turing machines simplify the statement of algorithms. Algorithms running on Turing-equivalent abstract machines are usually more general than their counterparts running on real machines, because they have arbitrary-precision datatypes available and never have to deal with unexpected conditions (including, but not limited to, running out of memory).

One way in which Turing machines are a poor model for programs is that many real programs, such as operating systems and word processors, are written to receive unbounded input over time, and therefore do not halt. Turing machines do not model such ongoing computation well (but can still model portions of it, such as individual procedures).

Another limitation of Turing Machines is that they do not model the strengths of a particular arrangement well. For instance, modern computers are actually instances of a more specific form of computing machine, known as the random access machine. The primary difference between this machine and the Turing Machine is that the Turing Machine uses an infinite tape, while the random access machine uses a numerically indexed sequence (typically an integer field). The upshot of this distinction is that there are computational optimizations that can be performed based on the memory indices, which are not possible in a general Turing Machine; thus when Turing Machines are used as the basis for bounding running times, a 'false lower bound' can be proven on certain algorithms' running times (due to the false simplifying assumption of a Turing Machine). An example of this is counting sort, which seemingly violates the lower bound on sorting algorithms.

A physical Turing machine

It is not difficult to simulate a Turing machine on a modern computer
(except for the limited memory of actually existing computers).

It is also possible to build a Turing machine on a purely mechanical basis.
The mathematician Karl Scherer has indeed built such a machine in 1986
using metal and plastic construction sets, and some wood.
The 1.5 meter high machine uses the pulling of strings to read, move and
write the data (which is represented using ball bearingss).

The machine is now exhibited in the entrance of the Department of Computer
Science of the University of Heidelberg, Germany.

Also, using a few hundred mirrors, one can build an optical universal Turing machine in one's backyard, using the Horseshoe map. This is based on a work by Stephen Smale.

The concept of a Turing machine was used as an educational tool in the science fiction novel The Diamond Age (1995), by Neal Stephenson. The main character, Nell, possesses an interactive book which teaches her creative thinking and logic by presenting puzzles in a story as Turing machines which become more and more complex as the story progresses. They begin as a simple chain-fed clockwork device and progresses to abstract economic processes, trades, and finally the interaction of entire fictional kingdoms.

References

Rolf Herken: The Universal Turing Machine - A Half-Century Survey, Springer Verlag, ISBN 3-211-82637-8

Paul Strathern: Turing and the Computer - The big idea, Anchor Books/Doubleday, ISBN 0-385-49243-X

Turing, A., On Computable Numbers, With an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David (ed.), The Undecidable, Hewlett, NY: Raven Press, 1965;

Boolos, G. and Jeffrey, R., Computability and Logic, 2nd ed., Cambridge: Cambridge University Press, 1980.

Rogozhin, Yurii, "A Universal Turing Machine with 22 States and 2 Symbols", Romanian Journal Of Information Science and Technology, 1(3), 259-265, 1998. (surveys known results about small universal Turing machines)

External links

Turing Machine on Stanford Encyclopedia of Philosophy

Detailed info on the Church-Turing Hypothesis (Stanford Encyclopedia of Philosophy)

Computing machinery and intelligence - A.M. Turing Original 1950 article by Alan Turing on machine intelligence, where he introduces the famous Turing test

The Turing test and intelligencedocument clarifying the meaning of the Turing test and suggests that meeting the Turing test is already in the process of being achieved

Citations from CiteSeer