…10110110111010….
It follows from this that any Turing machine has a finite encoding as a string on
{0,1} + and that, given any encoding of M, we can decode it uniquely. Some
strings will not represent any Turing machine (e.g., the string 00011), but we can
easily spot these, so they are of no concern.
A universal Turing machine M u then has an input alphabet that includes {0,
1} and the structure of a multitape machine, as shown in Figure 10.16.
For any input M and w, tape 1 will keep an encoded definition of M. Tape 2
will contain the tape contents of M, and tape 3 the internal state of M. M u looks
first at the contents of tapes 2 and 3 to determine the configuration of M. It then
consults tape 1 to see what M would do in this configuration. Finally, tapes 2 and
3 will be modified to reflect the result of the move.
It is within reason to construct an actual universal Turing machine (see, for
example, Denning, Dennis, and Qualitz 1978), but the process is uninteresting.
We prefer instead to appeal to Turing's hypothesis. The implementation clearly
can be done using some programming language; in fact, the program suggested
in Exercise 1, Section 9.1, is a realization of a universal Turing machine in a
higher-level language. Therefore, we expect that it can also be done by a
standard Turing machine. We are then justified in claiming the existence of a
Turing machine that, given any program, can carry out the computations
specified by that program and that is therefore a proper model for a generalpurpose computer.
Figure10.16
The observation that every Turing machine can be represented by a string of
It follows from this that any Turing machine has a finite encoding as a string on
{0,1} + and that, given any encoding of M, we can decode it uniquely. Some
strings will not represent any Turing machine (e.g., the string 00011), but we can
easily spot these, so they are of no concern.
A universal Turing machine M u then has an input alphabet that includes {0,
1} and the structure of a multitape machine, as shown in Figure 10.16.
For any input M and w, tape 1 will keep an encoded definition of M. Tape 2
will contain the tape contents of M, and tape 3 the internal state of M. M u looks
first at the contents of tapes 2 and 3 to determine the configuration of M. It then
consults tape 1 to see what M would do in this configuration. Finally, tapes 2 and
3 will be modified to reflect the result of the move.
It is within reason to construct an actual universal Turing machine (see, for
example, Denning, Dennis, and Qualitz 1978), but the process is uninteresting.
We prefer instead to appeal to Turing's hypothesis. The implementation clearly
can be done using some programming language; in fact, the program suggested
in Exercise 1, Section 9.1, is a realization of a universal Turing machine in a
higher-level language. Therefore, we expect that it can also be done by a
standard Turing machine. We are then justified in claiming the existence of a
Turing machine that, given any program, can carry out the computations
specified by that program and that is therefore a proper model for a generalpurpose computer.
Figure10.16
The observation that every Turing machine can be represented by a string of