A

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.