Turing machine an abstract automaton or imagined computer consisting of a finite automaton operating an indefinitely long storage tape. The finite automaton provides the computing power of the machine. The tape is used for input, output, and calculation workspace; in the case of the universal Turing machine, it also specifies another Turing machine. Initially, only a finite number of squares of the tape are marked with symbols, while the rest are blank. The finite automaton part of the machine has a finite number of internal states and operates discretely, at times t % 0, 1, 2, . . . . At each time-step the automaton examines the tape square under its tape head, possibly changes what is there, moves the tape left or right, and then changes its internal state. The law governing this sequence of actions is deterministic and is defined in a state table. For each internal state and each tape symbol (or blank) under the tape head, the state table describes the tape action performed by the machine and gives the next internal state of the machine. Since a machine has only a finite number of internal states and of tape symbols, the state table of a machine is finite in length and can be stored on a tape. There is a universal Turing machine Mu that can simulate every Turing machine (including itself): when the state table of any machine M is written on the tape of Mu, the universal machine Mu will perform the same input-output computation that M performs. Mu does this by using the state table of M to calculate M’s complete history for any given input. Turing machines may be thought of as conceptual devices for enumerating the elements of an infinite set (e.g., the theorems of a formal language), or as decision machines (e.g., deciding of any truth-functional formula whether it is a tautology). A. M. Turing showed that there are welldefined logical tasks that cannot be carried out by any machine; in particular, no machine can solve the halting problem.
Turing’s definition of a machine was theoretical; it was not a practical specification for a machine. After the modern electronic computer was invented, he proposed a test for judging whether there is a computer that is behaviorally equivalent to a human in reasoning and intellectual creative power.
The Turing test is a ‘black box’ type of experiment that Turing proposed as a way of deciding whether a computer can think. Two rooms are fitted with the same input-output equipment going to an outside experimenter. A person is placed in one room and a programmed electronic computer in the other, each in communication with the experimenter. By issuing instructions and asking questions, the experimenter tries to decide which room has the computer and which the human. If the experimenter cannot tell, that outcome is strong evidence that the computer can think as well as the person. More directly, it shows that the computer and the human are equivalent for all the behaviors tested. Since the computer is a finite automaton, perhaps the most significant test task is that of doing creative mathematics about the non-enumerable infinite.
See also BEHAVIORISM , COMPUTER THEORY, GÖDEL’ S INCOMPLETENESS THEOREMS , INFIN – ITY, LÖWENHEIM -SKOLEM THEORE. A.W.B.