Turing Machine

British mathematician Alan Turing (1912–1954) described what became known as the "Turing Machine" in his 1936 paper, "On Computable Numbers, with an application to the Entscheidungsproblem," which was published in the Proceedings of the London Mathematical Society in early 1937. The machine was actually a concept, not a piece of equipment, but its principles set the stage for the development of digital computers later in the twentieth century.

The machine can be described as a finite state control device (meaning that it has a finite number of states that control its operations), with a tape of unlimited length, divided into squares, upon which symbols may be written or stored. A sequence of actions can take place when a symbol is scanned by a read/write head and the machine is in a certain state. The sequence of actions is the "program."

At any point in time, the finite state control will be in one state and the tape head will be scanning a single symbol, or square, on the tape. On the basis of this symbol and the current state, it will write a symbol on the square, or choose to leave the symbol alone, move the tape one square to the left or the right, and change to a "new" (possibly the same) state. All this constitutes a "move" of the basic machine.

The purpose of the machine was to provide a method for deciding mathematical questions. Turing had become interested in the foundations of logic, and one of the unsolved or open questions was the "decideability" problem. The problem, posed in 1928 by German mathematician David Hilbert (1862–1943), was: "could there exist, at least in principle, a definite method or procedure by which all mathematical questions could be decided?"

The key to answering the question lay in the provision of a method, and this is what Turing's machine was to provide. The machine would be given a set of instructions to carry out some process or procedure, and the procedure would be carried out in order to answer a particular question. A different procedure would be provided for each problem. However, one could imagine a procedure for each particular problem being written on a single Turing Machine that would interpret the instructions to mimic or emulate the other machines.This would be a Universal Turing Machine, capable of carrying out any problem or program supplied to it.

The Turing Machine was intended to reproduce the actions or the activities of a human carrying out a computation. In this sense, it introduced a definition of computing that was "mechanical," i.e., it could be carried out by following a set of instructions. Thus, the Turing Machine can be considered as a device or a set of devices for carrying out an algorithm .

An algorithm is a mathematical procedure that comes to a halt after a finite number of steps, no matter what the values given for the variables. A mathematical procedure is one that can be performed mechanically, without risk of unexpected situations, once the value of the variables has been provided. A decision algorithm is one that gives a "yes" or "no" answer to a particular problem in a finite number of steps. A problem is said to be "algorithmically decideable" if a decision algorithm exists for it.

The Entscheidungsproblem, proposed by Hilbert in 1928 and written about by Turing in 1936, was the problem of decideability. Ultimately, Turing analyzed the formulas or functions of the predicate calculus or predicate logic and concluded that it was not possible, for a Turing Machine or other logical method, to answer all mathematical questions. This same conclusion was reached independently by Alonzo Church (1903–1995), an American logician, shortly before. Turing and Church later worked together at Princeton University, where Turing was a graduate student and Church a faculty member.

Turing developed this idea for a mathematical machine in 1936. He did so to answer a specific question. The Turing Machine's value extends beyond its inventor's original purpose, however. It provided an abstract model of computation, a conceptual device that could compute any effective procedure, i.e., one that comes to a halt after a finite number of steps. Although Turing's machine was never implemented, its conceptualization served as a model in the development of the digital computer, a machine that could be programmed to perform any computable task. The conceptual Turing Machine is still studied by computer scientists, logicians, and philosophers.

see also Turing, Alan M.

Roger R. Flynn

Bibliography

Boolos, George S., and Richard C. Jeffrey. Computability and Logic, 3rd ed. Cambridge, UK: Cambridge University Press, 1989.

Hodges, Andrew. Alan Turing: The Enigma of Intelligence. London: Unwin Paperbacks, 1983.

Strathern, Paul. Turing and the Computer. New York: Anchor Books, 1999.

Internet Resources

Buena Vista University. <http://www.bvu.edu/faculty/schweller/Turing.html>

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