Introduction
Every Turing machine computes a certain fixed partial computable function from the input strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, we can encode the action table of any Turing machine in a string. Thus we can construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and computes the tape that the encoded Turing machine would have computed. Turing described such a construction in complete detail in his 1936 paper:
- "It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D of some computing machine M, then U will compute the same sequence as M."
Read more about this topic: Universal Turing Machine
Famous quotes containing the word introduction:
“The role of the stepmother is the most difficult of all, because you can’t ever just be. You’re constantly being tested—by the children, the neighbors, your husband, the relatives, old friends who knew the children’s parents in their first marriage, and by yourself.”
—Anonymous Stepparent. Making It as a Stepparent, by Claire Berman, introduction (1980, repr. 1986)
“For the introduction of a new kind of music must be shunned as imperiling the whole state; since styles of music are never disturbed without affecting the most important political institutions.”
—Plato (c. 427–347 B.C.)
“We used chamber-pots a good deal.... My mother ... loved to repeat: “When did the queen reign over China?” This whimsical and harmless scatological pun was my first introduction to the wonderful world of verbal transformations, and also a first perception that a joke need not be funny to give pleasure.”
—Angela Carter (1940–1992)