“Turing machine”的概念、定义、翻译、参考文献-科学参考

Turing machine

Physics

A mathematical concept for deciding whether there is an algorithm for solving a mathematical problem. This concept has been applied to several issues in physics and may be fundamental. See also quantum Turing machine.

Mathematics

A theoretical machine which operates according to extremely simple rules, invented by Turing with the aim of obtaining a mathematically precise definition of what is computable. It has been generally agreed that the machine can calculate or compute anything for which there is an ‘effective’ algorithm (see Church’s thesis).

Statistics

A theoretical model of a computer, in which the machine functions in a sequence of discrete operations. The machine can be in only one of a finite list of internal states at any given moment. It consists of an infinite tape carrying symbols, which represent instructions, and a mechanism that can move the tape and read from, or write to, the tape. The mechanism can also change the internal state of the machine in accordance with instructions read from the tape.

Computer

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_{0}, \dots, s_{p}$
The control or processing unit of the machine can assume one of a finite number of distinct internal states:
$q_{0}, \dots, 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
$\begin{array}{l} q_{i} s_{j} s_{k} X q_{j} \\ where X is R, L, or N \end{array}$
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,
$\begin{array}{l} f : N^{k} \to N \\ where N = {0, 1, 2, \dots}, \\ N^{k} = N \times \dots \times N k times \end{array}$
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.

Electronics and Electrical Engineering

A mathematical model of a device that changes its internal state and reads from, writes on, and moves a potentially infinite tape, all in accordance with its present state, thereby constituting a model for computer-like behaviour. The model was published by Alan Turing in 1936.

Philosophy

A mathematical device used by the English mathematician Alan Turing (1912–54) to make precise the notion of an algorithm, or an effective computation. A Turing machine is a computer with a potentially infinite linear tape in both directions, divided into discrete squares that are scanned one at a time. Symbols in the squares are from a finite alphabet. The instructions for the machine are sets of ordered quintuples: <q_i, s_i, s_k, M, q_j> · q_i is the state the machine is in at the first moment, s_i is the symbol it reads on the square, s_k a symbol with which it replaces it, M is the instruction to move one square right or left or remain where it is, and q_j the state at the next moment. A function f(x) is Turing computable if, when some representation of the argument x is put on the tape, the machine halts on a representation of the value f(x). The class of Turing computable functions is identical with the class of general recursive functions (see also Church’s thesis).
http://www.turing.org.uk/philosophy/ex2.html An introduction by Turing’s biographer

单词	Turing machine
释义	Turing machine Physics A mathematical concept for deciding whether there is an algorithm for solving a mathematical problem. This concept has been applied to several issues in physics and may be fundamental. See also quantum Turing machine. Mathematics A theoretical machine which operates according to extremely simple rules, invented by Turing with the aim of obtaining a mathematically precise definition of what is computable. It has been generally agreed that the machine can calculate or compute anything for which there is an ‘effective’ algorithm (see Church’s thesis). Statistics A theoretical model of a computer, in which the machine functions in a sequence of discrete operations. The machine can be in only one of a finite list of internal states at any given moment. It consists of an infinite tape carrying symbols, which represent instructions, and a mechanism that can move the tape and read from, or write to, the tape. The mechanism can also change the internal state of the machine in accordance with instructions read from the tape. Computer 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_{0}, \dots, s_{p}$ The control or processing unit of the machine can assume one of a finite number of distinct internal states: $q_{0}, \dots, 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 $\begin{array}{l} q_{i} s_{j} s_{k} X q_{j} \\ where X is R, L, or N \end{array}$ 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, $\begin{array}{l} f : N^{k} \to N \\ where N = {0, 1, 2, \dots}, \\ N^{k} = N \times \dots \times N k times \end{array}$ 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. Electronics and Electrical Engineering A mathematical model of a device that changes its internal state and reads from, writes on, and moves a potentially infinite tape, all in accordance with its present state, thereby constituting a model for computer-like behaviour. The model was published by Alan Turing in 1936. Philosophy A mathematical device used by the English mathematician Alan Turing (1912–54) to make precise the notion of an algorithm, or an effective computation. A Turing machine is a computer with a potentially infinite linear tape in both directions, divided into discrete squares that are scanned one at a time. Symbols in the squares are from a finite alphabet. The instructions for the machine are sets of ordered quintuples: <q_i, s_i, s_k, M, q_j> · q_i is the state the machine is in at the first moment, s_i is the symbol it reads on the square, s_k a symbol with which it replaces it, M is the instruction to move one square right or left or remain where it is, and q_j the state at the next moment. A function f(x) is Turing computable if, when some representation of the argument x is put on the tape, the machine halts on a representation of the value f(x). The class of Turing computable functions is identical with the class of general recursive functions (see also Church’s thesis). http://www.turing.org.uk/philosophy/ex2.html An introduction by Turing’s biographer
随便看	single in-line devices single in, single out single instruction, multiple data single-lined binary single linkage clustering single-locus sequence typing single-loop feedback single market single-mode fibre single nucleotide polymorphism single-particle nanometry single-peaked preferences single phase single-phase system single-shot multivibrator single-shot trigger single-sideband modulation single-sideband transmission single-stage lead single-stage-to-orbit single-step operation singlet single threading singleton single-tuned circuit