Database Reference
In-Depth Information
r
I
1
(0
,
0)
R
(0)
R
(1)
.
Intuitively, the left branch is meant to represent a sequence of states with data values rep-
resenting registers while the right one is a sequence to represent natural numbers. We do
not have any equality test against a constant (say, a natural number). So, what we really do
is simulate values by the depth from the root. More concretely 0 and 1 above might as well
be
and
. Whatever they are, we simply take the value at the zeroth level as 0 and the first
level as 1, and so on. The above tree can be easily described by a DTD. To make sure it is
a proper run of the given machine, we use st-tgds
I
1
(1
,
0)
.
to check that the registers change their
values according to legal transitions.
Let us now describe the reduction in detail. A two-register machine
M
consists of a set
of states
Q
=
=(
I
i
i
∈
Q
\{
f
}
) (one instruction for
each state apart from the last state
f
), and two registers
r
1
and
r
2
, each containing a natural
number. A configuration of
M
is a triple (
i
,
m
,
n
) where
i
∈
Q
and
m
,
n
∈
N
{
1
,
2
,...,
f
}
, a list of instructions
I
are natural
numbers stored in
r
1
and
r
2
, respectively.
An instruction of a two-register machine is either an
increment
or a
decrement
,and
defines the transition relation
→
M
between configurations.
Increment
I
i
=(
r
,
j
),where
i
Q
and
r
is one of
r
1
and
r
2
. This means that
M
in state
i
increments
r
and goes to state
j
:
∈
(
j
,
m
+1
,
n
)
if
r
=
r
1
,
(
i
,
m
,
n
)
→
M
(
j
,
m
,
n
+1)
if
r
=
r
2
.
Decrement
I
i
=(
r
,
j
,
k
),where
i
,
j
,
k
∈
Q
and
r
is one of the two registers. This means that
M
in state
i
can test whether
r
is 0, and go to state
j
if it is, or decrement
r
and go
to
k
if it is not. In symbols,
⎧
⎨
(
j
,
0
,
n
)
if
r
=
r
1
and
m
= 0
,
(
j
,
m
−
1
,
n
)
if
r
=
r
1
and
m
= 0
,
(
i
,
m
,
n
)
→
M
⎩
(
j
,
m
,
0)
if
r
=
r
2
and
n
= 0
,
(
j
,
m
,
n
−
1)
if
r
=
r
2
and
n
= 0
.
The initial configuration is (1
,
0
,
0) and the final configuration is (
f
,
0
,
0). The halting
problem for a two-register machine is to decide, given a two-register machine
M
,whether
(1
,
0
,
0)
→
∗
M
(
f
,
0
,
0).
Let us now describe how to construct a mapping, which is consistent iff the given ma-