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-
 
Search WWH ::




Custom Search