Information Technology Reference
In-Depth Information
M
Q
B
B
BB
Fig. 6.6
The Turing machine
instructions defines the
computations
of
M
, as sequences of
configurations
gener-
ated in the following way.
A configuration is a string
(representing the tape content, with an un-
bounded number of blank symbol occurrences implicitly assumed on the left of
ϕ
ϕ
qx
ψ
A
∗
,
q
and on the right of
ψ
), where:
ϕ
,
ψ
∈
∈
Q
is the
current state
of the con-
figuration, and
x
∈
A
is the
current symbol
of the configuration. In the configuration
ϕ
x
as initial symbols can be applied.
M
is
determinis-
tic
when at most one instruction is applicable in every configuration, otherwise it is
nondeterministic
. The application of an instruction
qx
ψ
any instruction having
q
,
(
q
,
x
,
y
,
p
,
R
)
in the configuration:
ϕ
qx
ψ
yields a next configuration:
ϕ
yp
ψ
,
while an instruction
(
q
,
x
,
y
,
p
,
L
)
in the configuration:
ϕ
zqx
ψ
,
∈
where
z
A
is the symbol on the tape before the position of the current symbol
x
,
yields a next configuration:
ψ
.
The machine
M
starts a computation in an
initial configuration q
0
α
ϕ
pzy
A
∗
,where
α
∈
is the
input string
of the computation.
M
halts when no instruction is applicable. In this case, the configuration, say
ξ
,isa
final configuration
,andthe
output
of the corresponding computation
of
M
is the string
qx
χ
ξ
x
χ
(where the symbol of the state is removed from the final
configuration).
}
∗
of type
1
n
+
1
B
1
m
+
1
provides as result 1
n
+
m
+
1
(1
n
+
1
is a representation of number
n
).
The Turing machine of Table 6.13 when starts with a string of
{
B
,
1
