About Opentopia
Opentopia Directory Encyclopedia Tools

Turing machine

Encyclopedia : T : TU : TUR : Turing machine

An artistic representation of a Turing Machine .
Enlarge
An artistic representation of a Turing Machine .

For Alan Turing's test devised to determine the quality of an artificial intelligence, see Turing test
Turing machines are extremely basic symbol-manipulating devices which — despite their simplicity — can be adapted to simulate the logic of any computer that could possibly be constructed. They were described in 1936 by Alan Turing. Though they were intended to be technically feasible, Turing machines were not meant to be a practical computing technology, but a thought experiment about the limits of mechanical computation; thus they were not actually constructed. Studying their abstract properties yields many insights into computer science and complexity theory.

A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine). A more mathematically-oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–Turing thesis. The thesis states that Turing machines indeed capture the informal notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or 'mechanical procedure'.

Contents

Single-tape machines

Informal description

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 unlimited paper tape, which is divided into squares 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', move one symbol to the right, and assume state 17 as your new state."

A Turing machine is equivalent to a pushdown automaton made more powerful by relaxing the last-in-first-out requirement of its stack. (Interestingly, this 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:

  1. 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 extensible 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.
  2. A head that can read and write symbols on the tape and move left and right one (and only one) step at a time.
  3. 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.
  4. 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; it is the potentially unlimited amount of tape that gives it an unbounded amount of storage space.

Example

The example Turing machine handles a string of 0s and 1s, with 0 represented by the blank symbol. Its task is to double any series of 1s encountered on the tape by writing a 0 between them. For example, when the head reads "111", it will write a 0, then "111". The output will be "1110111".

In order to accomplish its task, this Turing machine will need only 5 states of operation, which are called . Each state does 4 actions:

1) Read the symbol under the head

2) Write the output symbol decided by the state

3) Move the head to the left or to the right decided by the state

4) Switch to the following state decided by the current state

The actions of each state are defined by the following action table:

Old Read   Wr.      New
St. Sym.   Sym. Mv. St.
- - - - - - - - - - - -
s1  1  ->  0    R   s2
s2  1  ->  1    R   s2
s2  0  ->  0    R   s3
s3  0  ->  1    L   s4
s3  1  ->  1    R   s3
s4  1  ->  1    L   s4
s4  0  ->  0    L   s5
s5  1  ->  1    L   s5
s5  0  ->  1    R   s1

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
- - - - - - - -
01  s1   11
02  s2   01
03  s2   010
04  s3   0100
05  s4   0101
06  s5   0101
07  s5   0101
08  s1   1101
09  s2   1001
10  s3   1001
11  s3   10010
12  s4   10011
13  s4   10011
14  s5   10011
15  s1   11011
-- 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 1s and the first 0 encountered. s3 then skips over the next sequence of 1s (initially there are none) and replaces the first 0 it finds with a 1. s4 moves back to the left, skipping over 1s until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1s 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 in the middle of the two strings of 1s) at which time the machine halts.

Formal definition

More formally, a (one-tape) Turing machine is usually defined as a 6-tuple [M= \langle Q, \Gamma, s, b, F, \delta \rangle] where

Definitions in 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.

Multi-tape machines

In practical analysis, various types of multi-tape Turing machines are often used. Multi-tape machines are similar to single-tape machines, but there is some constant k number of independent tapes. Each tape has a separate read/write head. The transition rules depend on the symbols underneath each of the k heads at once.

This model intuitively seems much more powerful than the single-tape model, but any multi-tape machine, no matter how large the k, can be simulated by a single-tape machine using only quadratically more computation time (Papadimitriou 1994, Thrm 2.1). Thus, multi-tape machines cannot calculate any more functions than single-tape machines, and none of the robust complexity classes (such as polynomial time) are affected by a change between single-tape and multi-tape machines.

Formal definition

A k-tape Turing machine can be described as a 6-tuple [M=\langle Q, \Gamma, s, b, F, \delta \rangle] where

Machines with input and output

It is difficult to study sublinear space complexity on multi-tape machines with the traditional model, because an input of size n already takes up space n. Thus, to study small DSPACE classes, we must use a different model. In some sense, if we never "write to" the input tape, we don't want to charge ourself for this space. And if we never "read from" our output tape, we don't want to charge ourself for this space.

We solve this problem by introducing a k-string Turing machine with input and output. This is the same as an ordinary k-string Turing machine, except that the transition function [\delta] is restricted so that the input tape can never be changed, and so that the output head can never move left. This model allows us to define deterministic space classes smaller than linear. Turing machines with input-and-output also have the same time complexity as other Turing machines; in the words of Papaditriou 1994 Prop 2.2:

For any k-string Turing machine M operating within time bound f(n)) there is a (k+2)-string Turing machine M’ with input and output, which operates within time bound O(f(n)).
k-string Turing machines with input and output are used in the formal definition of the complexity resource DSPACE in, for example, Papadimitriou 1994 (Def. 2.6).

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). The two are computationally equivalent, that is, it is possible to turn any NDTM into a DTM (and vice versa).

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, we can encode the action table of any Turing machine in a string. Thus we can construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and computes the tape that the encoded Turing machine would have computed. Turing described such a construction in some detail in his 1936 paper.

In 1947, Turing said:

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.

This was, perhaps, the seminal theoretical idea for operating system, a program to run (controlledly) other programs...showing that its existence was possible and encouraging the plausiblity of investing in practical applications.

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

If we define "universal Turing machine" 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.

For some time, the smallest known universal Turing machines, which simulated a computational model called a tag system, had the following numbers of states and symbols : 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 24×2. (For example, see Minsky Chapter 14.8.1 p. 277 for a detailed description of a tag-system-based 4x7 machine.) Wolfram reports in his book, A New Kind of Science, a smaller universal Turing machine with 2 states and just 5 symbols, which emulates a cellular automaton also known to be universal, making this the simplest known universal Turing machine.

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.

An abstract version of the universal Turing machine is the universal function, a computable function which can be used to calculate any other computable function. The utm theorem proves the existence of such a function.

Comparison with real machines

It is 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 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 unlimited 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:

  1. Anything a real computer can compute, a Turing machine can also compute. Thus, a statement about the limitations of Turing machines will also apply to real computers.
  2. The difference lies only with the ability of a Turing machine to manipulate an unbounded amount of data. However, given a finite amount of time, a Turing machine (like a real machine) can only manipulate a finite amount of data.
  3. Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media. If the supply of these runs short, the Turing machine may become less useful as a model. But the fact is that neither Turing machines nor real machines need astronomical amounts of storage space in order to perform useful computation. The processing time required is usually much more of a problem; see busy beaver for examples of machines that perform a very large number of steps using only a tiny number of bits.
  4. 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 deterministic finite automaton on a given real machine has quadrillions. This makes the DFA representation infeasible to analyze.
  5. Turing machines describe algorithms independent of how much memory they utilize. There is a limit to the memory possessed by any current machine, 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.
  6. 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 data types 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 Ω(n log n) lower bound on sorting algorithms. Another is binary search, which violates the Turing machine's linear Ω(n) lower bound on searching an ordered list.

Models equivalent to the Turing machine model

Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p. 159, cf Minsky). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the Church-Turing thesis hypothesizes this to be true: that anything that can be “computed” can be computed by some Turing machine.)

At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational power as the Turing machine model. A prime example (see Post-Turing Machine) is the model introduced by Emil Post in a paper received for publication in October 1936. (This was several months after Turing’s paper was received in May 1936, although the latter wasn't published until January 1937.) Post described his system, called Formulation 1, as a process in which there is a given two-way infinite sequence of boxes, each of which is either marked or unmarked (with finitely-many initially marked), and a worker follows a finite set of numbered instructions to move among and mark/unmark the boxes. The worker is to start at a specified box and follow the instructions (which are numbered consecutively as 1, 2, 3, ...) starting with instruction 1, the i th instruction being one of the following types:

:* mark/unmark the current box (assumed unmarked/marked, resp.) and goto instruction ji
:* move right/left one box and goto instruction ji
:* if the current box is marked then go to instruction ji′ else goto instruction ji′′
:* stop
This extremely simple model can emulate any Turing machine, and although Formulation 1 does not use the word "program" or "machine", it is effectively a formulation of a very primitive programmable computer and associated programming language, with the boxes acting as an unbounded bitstring memory, and the set of instructions constituting a program.

Some alternate constructions include those described by Hopcroft and Ullman, Chapter 7.5 and 7.8 :

:* 4-counter machines
:* 2-counter machines
  • Machines with restricted symbols such as “0” and “1” (e.g. the Post model above)
    • Marvin Minsky (cf Chapters 11 and 14) describes a computational model “similar to computers” that has been shown to be equivalent in computational power to a Turing machine. This Minsky machine has only two instructions:
    (1) Add 1 to the number in register a, and go to next instruction,
    (2) If number in a is not zero then subtract 1 from a and go to the next instruction, otherwise go to the nth instruction.
    Minsky then shows that the following are equivalent to Turing machines: Normal Markov Algorithm is another remarkably simple computational model equivalent to the Turing machines.

    See also

    References

    External links

    Simulators

    Automata theory: formal languages and formal grammars
    Chomsky
    hierarchy         		Grammars Languages Minimal
    automaton
    Type-0 Unrestricted Recursively enumerable Turing machine
    n/a (no common name) Recursive Decider
    Type-1 Context-sensitive Context-sensitive Linear-bounded
    Type-2 Context-free Context-free Pushdown
    Type-3 Regular Regular Finite
    Each category of languages or grammars is a proper subset of the category directly above it.

     

    From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
    All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

    Search Titles
    0123456789
    ABCDEFGHIJ
    KLMNOPQRST
    UVWXYZ?

    E-mail this article to:

    Personal Message: