[ Pobierz całość w formacie PDF ]
grammed for a two-tape Turing Machine in such a way that U does not have to write on the tapes, in order
to remember the intermediate result of such actions as searching a matching string . In other words, can
we be sure that at any moment of its computation, the content of the tapes of U can be interpreted as the
encoded program of M or the encoded state plus encoded tape of T , respectively?
This afterthought is partially addressed by Hopcroft and Ullman in [4]. They propose a universal ma-
chine M1 that uses three tapes: one for the (encoded) program and input; one for the (encoded) simulated
tape; and one tape for the (encoded) state. The unused part of the third tape may be used as a scratch-
pad , so we can be fairly confident that first two tapes contain valid encodings at all times. Note that the
translation of machines with multiple tapes to machines with one tape involves an explosion of symbols
[4, Theorems 7.1 & 7.2]. If we consider a one-tape universal machine, we don t have a clean separation of
encoded program, encoded tape, and scratchpad.
Also note that Hopcroft and Ullman construct a machine that is constructed to be universal for Turing
Machines that accept input strings, not for machines that compute functions on input strings.
1.5.2 Turing s Universal Machine
We would like to give a very short introduction to Turing s original universal computing machine . For
an overview of Turing s computing machines, see Section 1.4; we build upon the notions detailed in that
section. First of all, let us note that Turing s approach has the following properties:
" By representing states and symbols as unary strings with distinguishable separators, Turing can en-
code the program of any machine.
" The machine uses a single tape.
" The machine has squares that are write-once (the F-squares) and that contain all the information
about the simulated machine: encoded program, encoded tape content and encoded state. Other
squares (the E-squares) are used solely for the computation of the universal machine itself.
" The universal machine keeps track of the entire computation of the simulated machine, not just the
current tape and state at any given time.
Definition 1.54 (Turing s encoding). We translate the states qi (0 d" i
quintuples to a string over alphabet {A, C, D, L, R, N, ; , :, ::} by the function below. (Think of the symbol D
as delimiter ).
translation(qi) = DCi
translation(si) = DAi
translation((qa, sb, qc, X, sd)) = DCaDAbDCcXDAd for X " {L, R, N}
1.5. UNIVERSAL TURING MACHINES 25
Figure 1.9 Example tape content of Turing s universal machine
In this example we only show the content of the F-squares (white). We have a left-hand marker followed
by a description of a machine program In the program, each coded quintuple is separated by a semicolon.
The end of the program is marked with a double-colon (::). After that, we see three sequences separated
by colons. Each such sequence is a complete configuration , encoding the tape content, tape head position
and state. If we leave out the E-squares we can read the example as in Table 1.5.
. . .
; ;
D A D D C R D A A
:: : :
D A D D C D A A D
. . .
:
D C D D A A D
Table 1.5 Interpreting the Universal Turing Machine tape
We interpret the example of Figure 1.9 by assuming that the simulated machine uses figures s0 = , s1 = 0,
s2 = 1. The left-hand side symbol is not explicitly encoded, so we start each tape with .
Type Symbols Value Interpretation
Program quintuples DADDCRDAA q1s0s1Rq2 (a, , 0, R, b)
. . . . . . . . .
Type Symbols Value Interpretation
State Tape Position
Complete configuration DAD q1s0 q1 1
DCDAAD s1q2s0 q2 0 2
DCDDAAD s1s0q2s0 q2 0 3
Figure 1.9 is an example due to [13]. To determine the computed sequence of the simulated machine,
we have to look at the machine configurations of the simulated machine that U writes on the tape. Each
progressive configuration may contain a new figure. It is possible, but non-trivial, to filter out these printed
figures and determine the entire computed sequence of the simulated machine.
A Universal Turing Machine is itself not a Turing Machine in the strictest sense. After all, the machine
is started with some symbols on the tape, and not with a blank tape. However, the mechanical machine
itself is unchanged.
1.5.3 Universal Talkative Machine
In Section 1.4.3 we defined Talkative Turing Machines , a concept that unifies the interpretation as function [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl ocenkijessi.opx.pl
grammed for a two-tape Turing Machine in such a way that U does not have to write on the tapes, in order
to remember the intermediate result of such actions as searching a matching string . In other words, can
we be sure that at any moment of its computation, the content of the tapes of U can be interpreted as the
encoded program of M or the encoded state plus encoded tape of T , respectively?
This afterthought is partially addressed by Hopcroft and Ullman in [4]. They propose a universal ma-
chine M1 that uses three tapes: one for the (encoded) program and input; one for the (encoded) simulated
tape; and one tape for the (encoded) state. The unused part of the third tape may be used as a scratch-
pad , so we can be fairly confident that first two tapes contain valid encodings at all times. Note that the
translation of machines with multiple tapes to machines with one tape involves an explosion of symbols
[4, Theorems 7.1 & 7.2]. If we consider a one-tape universal machine, we don t have a clean separation of
encoded program, encoded tape, and scratchpad.
Also note that Hopcroft and Ullman construct a machine that is constructed to be universal for Turing
Machines that accept input strings, not for machines that compute functions on input strings.
1.5.2 Turing s Universal Machine
We would like to give a very short introduction to Turing s original universal computing machine . For
an overview of Turing s computing machines, see Section 1.4; we build upon the notions detailed in that
section. First of all, let us note that Turing s approach has the following properties:
" By representing states and symbols as unary strings with distinguishable separators, Turing can en-
code the program of any machine.
" The machine uses a single tape.
" The machine has squares that are write-once (the F-squares) and that contain all the information
about the simulated machine: encoded program, encoded tape content and encoded state. Other
squares (the E-squares) are used solely for the computation of the universal machine itself.
" The universal machine keeps track of the entire computation of the simulated machine, not just the
current tape and state at any given time.
Definition 1.54 (Turing s encoding). We translate the states qi (0 d" i
quintuples to a string over alphabet {A, C, D, L, R, N, ; , :, ::} by the function below. (Think of the symbol D
as delimiter ).
translation(qi) = DCi
translation(si) = DAi
translation((qa, sb, qc, X, sd)) = DCaDAbDCcXDAd for X " {L, R, N}
1.5. UNIVERSAL TURING MACHINES 25
Figure 1.9 Example tape content of Turing s universal machine
In this example we only show the content of the F-squares (white). We have a left-hand marker followed
by a description of a machine program In the program, each coded quintuple is separated by a semicolon.
The end of the program is marked with a double-colon (::). After that, we see three sequences separated
by colons. Each such sequence is a complete configuration , encoding the tape content, tape head position
and state. If we leave out the E-squares we can read the example as in Table 1.5.
. . .
; ;
D A D D C R D A A
:: : :
D A D D C D A A D
. . .
:
D C D D A A D
Table 1.5 Interpreting the Universal Turing Machine tape
We interpret the example of Figure 1.9 by assuming that the simulated machine uses figures s0 = , s1 = 0,
s2 = 1. The left-hand side symbol is not explicitly encoded, so we start each tape with .
Type Symbols Value Interpretation
Program quintuples DADDCRDAA q1s0s1Rq2 (a, , 0, R, b)
. . . . . . . . .
Type Symbols Value Interpretation
State Tape Position
Complete configuration DAD q1s0 q1 1
DCDAAD s1q2s0 q2 0 2
DCDDAAD s1s0q2s0 q2 0 3
Figure 1.9 is an example due to [13]. To determine the computed sequence of the simulated machine,
we have to look at the machine configurations of the simulated machine that U writes on the tape. Each
progressive configuration may contain a new figure. It is possible, but non-trivial, to filter out these printed
figures and determine the entire computed sequence of the simulated machine.
A Universal Turing Machine is itself not a Turing Machine in the strictest sense. After all, the machine
is started with some symbols on the tape, and not with a blank tape. However, the mechanical machine
itself is unchanged.
1.5.3 Universal Talkative Machine
In Section 1.4.3 we defined Talkative Turing Machines , a concept that unifies the interpretation as function [ Pobierz całość w formacie PDF ]