The Turing machine is an abstract (71) of computer execution and storage introduced in 1936 by Alan Turing to give a mathematically precise definition of (72) . or ’mechanical procedure’. As such it is still widely used in theoretical computer science, especially in (73) theory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as Turing’s thesis.
Every Turing machine computes a certain (74) partial function over the strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, as Alan luring already described, we can encode the action table of every Turing machine in a string. Thus we might try to construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape that the encoded Turing machine would have computed. As Turing showed, such a luring machine is indeed possible and since it is able to simulate any other Turing machine it is called a (75) Turing machine.
A universal Turing machine is Turing complete. It can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. According to the Church-Turing thesis, the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.
（73）处填（）。
A．intricacy
B．complexity
C．complicacy
D．difficulty
