Turing machine

Home > Science and Technology > Computers and Electrical Engineering > Computers and Computing

Turing machine (TM) An imaginary computing machine defined as a mathematical abstraction by Alan Turing to make precise the notion of an effective procedure (i.e. an algorithm). There are many equivalent ways of dealing with this problem; among the first was Turing's abstract machine, published in 1936.

A Turing machine is an automaton that includes a linear tape that is potentially infinite (in both directions), divided into boxes or cells, and read by a read-head that scans one cell at a time. Symbols written on the tape are drawn from a finite alphabet: s₀,…,s_p

The control or processing unit of the machine can assume one of a finite number of distinct internal states: q₀,…,q_m

The “program” for a given machine is assumed to be made up from a finite set of instructions that are quintuples of the form q_is_js_kXq_j where X is R, L, or N

The first symbol indicates that the machine is in state q_i while the second indicates that the head is reading s_j on the tape. In this state the machine will replace s_j by s_k and if X = R the head will move to the right; if X = L it will move to the left and if X = N it will remain where it is. To complete the sequence initiated by this triple the machine will go into state q_j.

The machine calculates functions on the natural numbers as follows: a function f, f : N^k → N where N = {0,1,2,…}, N^k = N × … × N k times

is (Turing) computable if for each x in N^k, when some representation of x in N^k is placed on the tape (with the machine in the initial state of q₀ say), the machine halts with a representation of f(x) on the tape. See also effective computability.

It is customary in the study of abstract computation models to make a distinction between deterministic and nondeterministic algorithms. In a deterministic Turing machine the overall course of the computation is completely determined by the Turing machine (program), the starting state, and the initial tape-inputs; in a nondeterministic Turing machine there are several possibilities at each stage of the computation: it can execute one out of possibly several machine instructions. The class of problems solvable by deterministic Turing machines in polynomial time is the class P; the class of problems solvable by nondeterministic Turing machines in polynomial time is the class NP. See also P=NP question.

Turing machine a mathematical model of a device that computes via a series of discrete steps and is not limited in use by a fixed maximum amount of data storage. Introduced by the British mathematician Alan Turing in 1936, a Turing machine is a particularly simple computer , one whose operations are limited to reading and writing symbols on tape, or moving along the tape to the left or to the right one symbol at a time. Its behavior at a given moment is determined by the symbol in the square currently being read and by the current state of the machine. The theoretical prototype of the electronic digital computer, Turing machines are one of the key abstractions used in modern computability theory, the study of what computers can and cannot do. Appropriate Turing machines have found application in the study of artificial intelligence, the structure of languages, and pattern recognition.

Turing machine a mathematical model of a hypothetical computing machine which can use a predefined set of rules to determine a result from a set of input variables. It is named for the English mathematician Alan Mathison Turing (1912–54), who developed the concept of a theoretical computing machine, a key step in the development of the first computer, and carried out important code-breaking work in the Second World War.