Turing machine
Turing machine
Turing machine
Tu′ring machine`
(ˈtʊər ɪŋ, ˈtyʊər-)n.
| Noun | 1. |  Turing machine - a hypothetical computer with an infinitely long memory tape |
| 单词 | turing machine | |||
| 释义 | Turing machineTuring machineTuring machineTu′ring machine`(ˈtʊər ɪŋ, ˈtyʊər-)n.
Turing MachineTuring machine,a mathematical model of a device that computes via a series of discrete steps and is not limited in use by a fixed maximum amount of data storage. Introduced by the British mathematician Alan TuringTuring, Alan Mathison,1912–54, British mathematician and computer theorist. While studying at Cambridge he began work in predicate logic that led to a proof (1937) that some mathematical problems are not susceptible to solution by automated computation; in arriving at ..... Click the link for more information. in 1936, a Turing machine is a particularly simple computercomputer, device capable of performing a series of arithmetic or logical operations. A computer is distinguished from a calculating machine, such as an electronic calculator, by being able to store a computer program (so that it can repeat its operations and make logical ..... Click the link for more information. , one whose operations are limited to reading and writing symbols on tape, or moving along the tape to the left or to the right one symbol at a time. Its behavior at a given moment is determined by the symbol in the square currently being read and by the current state of the machine. The theoretical prototype of the electronic digital computer, Turing machines are one of the key abstractions used in modern computability theory, the study of what computers can and cannot do. Appropriate Turing machines have found application in the study of artificial intelligence, the structure of languages, and pattern recognition. Turing Machinethe name applied to abstract, or conceptual, “computing machines” of a certain precisely described type that provide a precise version, suitable for the purposes of mathematical consideration, of the general intuitive idea of an algorithm. The concept of such a machine was formulated in the mid-1930’s by A. M. Turing as a result of his analysis of the actions of a person carrying out certain calculations, that is, successive transformations of complexes of symbols, in accordance with a previously developed plan. It is convenient to regard a Turing machine as an automatically operating device that is capable of being in a finite number of internal states and is provided with an infinite external memory, a tape. Among the states are two special ones, the initial state and the final state. The tape is divided into squares and is unbounded to the right and to the left. Any symbol included in some previously given list may be written in each square of the tape (for uniformity it is assumed that a blank is written in an empty square). At every moment in time the Turing machine is in one of its states; in this state it scans a square of the tape by means of a special apparatus and reads the symbol written in that square. If the Turing machine is in a nonfinal state at a given moment in time, then at the next moment the machine executes one of the following operations: (1) it changes to a new state, which may be, for example, the final state or the same as the old state; (2) it replaces the old symbol in the square being scanned with a new symbol, which may be, for example, a blank or the same symbol as the old one; and (3) it shifts the tape one square to the left or right or holds the tape in place. Such a step of the Turing machine is completely determined by the machine’s state at a given moment and the symbol being read. A table that contains the full list of possible steps for a given Turing machine is called the program of the machine. A complete description of a Turing machine at a given moment is given by its configuration, which is a specification of the following information for the given moment: (1) the actual symbols contained in the squares of the tape, (2) the square being read by the machine, and (3) the state of the machine. If any configuration with a nonfinal state is taken as an initial configuration of a given Turing machine, then the operation of the machine will consist in the sequential step-by-step transformation of the initial configuration in accordance with the machine’s program until a configuration with a final state is attained. The latter configuration, if it exists, is considered the result of the operation of the given Turing machine on the initial configuration. Strong arguments exist for considering that the concept of a Turing machine supplies an adequate precise formulation of the general concept of an algorithm, that is, that any algorithm can be modeled by a suitable Turing machine. This hypothesis is known in the theory of algorithms as Turing’s thesis. The theory of Turing machines provides a convenient working apparatus for many studies that require a precise definition of an algorithm. In particular, because of the naturalness of the steps executed by Turing machines, the machines have become the object of close attention in the theory of the complexity of algorithmic computations. In the course of the development of the theory of Turing machines, various generalizations of the machines have been considered, for example, Turing machines with a more general type of tape, machines with several tapes, and nondeterministic Turing machines. REFERENCESKleene, S. C. Vvedenie v metamatematiku. Moscow, 1957. (Translated from English.)Mendelson, E. Vvedenie v matematicheskuiu logiku. Moscow, 1971. (Translated from English.) N. M. NAGORNYI Turing machine[′tu̇r·iŋ mə‚shēn]Turing Machine(computability)In an alternative scheme, the machine writes a symbol to thetape *and* moves at each step. This can be encoded as a writestate followed by a move state for the write-or-move machine.If the write-and-move machine is also given a distance to movethen it can emulate an write-or-move program by using stateswith a distance of zero. A further variation is whetherhalting is an action like writing or moving or whether it is aspecial state. Without loss of generality, the symbol set can be limited tojust "0" and "1" and the machine can be restricted to start onthe leftmost 1 of the leftmost string of 1s with strings of 1sbeing separated by a single 0. The tape may be infinite inone direction only, with the understanding that the machinewill halt if it tries to move off the other end. All computer instruction sets, high level languages andcomputer architectures, including parallel processors, canbe shown to be equivalent to a Turing Machine and thusequivalent to each other in the sense that any problem thatone can solve, any other can solve given sufficient time andmemory. Turing generalised the idea of the Turing Machine to a"Universal Turing Machine" which was programmed to readinstructions, as well as data, off the tape, thus giving riseto the idea of a general-purpose programmable computingdevice. This idea still exists in modern computer design withlow level microcode which directs the reading and decodingof higher level machine code instructions. A busy beaver is one kind of Turing Machine program. Dr. Hava Siegelmann of Technion reported in Science of 28Apr 1995 that she has found a mathematically rigorous class ofmachines, based on ideas from chaos theory and neural networks, that are more powerful than Turing Machines. SirRoger Penrose of Oxford University has argued that the braincan compute things that a Turing Machine cannot, which wouldmean that it would be impossible to create artificial intelligence. Dr. Siegelmann's work suggests that this istrue only for conventional computers and may not cover neural networks. See also Turing tar-pit, finite state machine. Turing machine
Words related to Turing machine
|
|||
| 随便看 |
|
英语词典包含2567994条英英释义在线翻译词条，基本涵盖了全部常用单词的英英翻译及用法，是英语学习的有利工具。