| 释义 |
Turing machine|ˈtjʊərɪŋ|
[Named after A. M. Turing (1912–54), English mathematician, who described such a machine in 1936.]
A notional computing machine for performing simple reading, writing, and shifting operations in accordance with a prescribed set of rules, invoked in theories of computability and automata.
It is represented as a scanner that has a number of internal states and moves left or right along a tape on which is a sequence of symbols. The symbol read and the state of the scanner determine (in accordance with the rules) what replacement symbol is written, what new state the scanner enters, and what move it makes along the tape before the cycle is repeated.
1937A. Church in Jrnl. Symbolic Logic II. 43 [Abstract of Turing's paper.] Certain further restrictions are imposed on the character of the machine, but these are of such a nature as obviously to cause no loss of generality—in particular, a human calculator, provided with pencil and paper and explicit instructions, can be regarded as a kind of Turing machine. 1955Sci. Amer. Apr. 62/1 To understand a Turing machine we need only know its table of commands. 1961Proc. Symposium Appl. Math. XII. 39 A Turing machine plus random elements is a reasonable model for the human brain. 1969P. B. Jordain Condensed Computer Encycl. 550 No Turing machine has ever been physically constructed or realized in hardware as a device for its own sake, but general-purpose digital computers have been programmed to simulate Turing machines. 1984Sci. Amer. May 70/1 Beginning with the intuitive idea that a method is an algorithm—a procedure that can be mechanically carried out without creative intervention—he [sc. A. M. Turing] showed how the idea can be refined into a detailed model of the process of computation in which any algorithm is broken down into a sequence of simple, atomic steps. The resulting model of computation is the logical construct called a Turing machine. |