Information Technology Reference
In-Depth Information
Without loss of generality we consider only deterministic Turing machines
M
=(Γ
,
β
,
Q
,
δ
,
s
,
h
) that have a binary tape alphabet
Γ=
B
=
{
}
.When
M
is in state
p
and the
0, 1
value under the head is
a
, the next-state function
δ
:
Q
×
(Γ
∪{
β
}
)
→
(
Q
∪{
h
}
)
×
(Γ
∪{
β
}∪{
}
)
takes
M
to state
q
and provides output
z
,where
δ
(
p
,
a
)=(
q
,
z
)
and
L
,
R
z
∈
Γ
∪{
β
}∪{
}
.
We now specify a convention for numbering states that simplifies the description of the
next-state function
δ
of
M
.
DEFINITION
5.5.1
The
canonical encoding
of a Turing machine
M
,
ρ
(
M
)
,isastringoverthe
10-letter alphabet
Λ=
L
,
R
{
<
,
>
,
[
,
]
,
#
,0,1,
β
,
R
,
L
}
formed as follows:
where
s
=
q
1
. Represent state
q
i
in unary notation by the string
1
i
. The halt state
h
is represented by the empty string.
(b) Let
(
q
,
z
)
be the value of the next-state function when
M
is in state
p
reading
a
under
its tape head; that is,
δ
(
p
,
a
)=(
q
,
z
)
.Represent
(
q
,
z
)
by the string
<z
#
q>
in which
q
is
represented in unary and
z
(a) Let
Q
=
{
q
1
,
q
2
,
...
,
q
k
}
∈{
0, 1,
β
,
L
,
R
}
.If
q
=
h
, the value of the next-state function is
<z
#
>
.
(c) For
p
Q
,thethreevalues
<z
#
q
>
,
<z
#
q
>
,and
<z
#
q
>
of
δ
(
p
,0
)
,
δ
(
p
,1
)
,and
δ
(
p
,
β
)
are assembled as a triple
[
<z
#
q
>< z
#
q
>< z
#
q
>
]
.The
complete description of the next-state function
δ
is given as a sequence of such triples, one for each
state
p
∈
∈
Q
.
To illustrate this definition, consider the two TMs whose next-state functions are shown in
Fig.
5.3
. The first moves across the non-blank initial string on its tape and halts over the first
blank symbol. The second moves the input string right one position and inserts a blank to its
left. The canonical encoding of the first TM is
[
<
R
#
1
><
R
#
1
><β
#
>
]
whereas that
of the second is
[
<β
#
11
><
#
111
><
#
>
]
[
<
R
#
1111
><
R
#
1111
><
R
#
1111
>
]
[
<
R
#
11111
><
R
#
11111
><
R
#
11111
>
]
[
<
0
#
11
><
0
#
111
><
0
#
>
]
[
<
1
#
11
><
1
#
111
><
1
#
>
]
It follows that the canonical encodings of TMs are a subset of the strings defined by the
regular expression
([(
<
#
1
∗
>
)
3
])
∗
which a TM can analyze to insure that for
each state and tape letter there is a valid action.
A
universal Turing machine
(UTM)
U
is a Turing machine that is capable of simulating
an arbitrary Turing machine on an arbitrary input word
w
. The construction of a UTM based
on the simulation of the random-access machine is described in Section
3.8
. Here we describe
a direct construction of a UTM.
Let the UTM
U
have a 20-letter alphabet
Λ
containing the 10 symbols in
Λ
plus another
10 symbols that are marked copies of the symbols in
Λ
.(Themarkedcopiesareusedto
simulate multiple tracks on a one-track TM.) That is, we define
Λ
as follows:
Λ=
{
0, 1,
β
,
L
,
R
}
}∪{<
,
>
,
[
,
]
,
#
, 0, 1,
β
,
R
,
L
{
<
,
>
,
[
,
]
,
#
,0,1,
β
,
R
,
L
}
To simulate the TM
M
on the input string
w
,weplace
M
's canonical encoding,
ρ
(
M
)
,
onthetapeoftheUTM
U
preceded by
β
andfollowedby
w
, as suggested in Fig.
5.10
.The
Search WWH ::
Custom Search