Database Reference
In-Depth Information
We now define a target schema R
t
such that instances of R
t
describe finite computations
of Turing machines. But first we need to introduce some terminology.
A
computation
of
A
is a sequence (
c
0
,
c
1
,...,
c
n
) of
configurations
,
n
≥
1, such that:
1.
c
0
is the
initial
configuration, and
2. for each
i
<
n
,
c
i
+1
is the
successor
configuration of
c
i
.
The computation is
halting
if
c
n
is a halting configuration. As will become clear after
we define configurations,
A
halts on the empty input if and only if there is a halting
computation of
A
.
Each configuration
c
j
,for0
≤
j
≤
n
, can be represented as a tuple (
q
j
,
i
j
,
a
j
)
∈
Q
×
N
×
A
j
+2
,where:
•
q
j
represents the state of
A
in
c
j
,
•
i
j
represents the position of the head of
in
c
j
(which can be assumed to be a nonneg-
ative integer since the head never moves to the left of the initial position), and
A
•
a
j
is the tuple (
a
j
,
0
,...,
a
j
,
j
+1
),where
a
j
,
represents the symbol that appears in position
,for0
≤
≤
A
can visit at most
j
positions in
j
steps, we can assume
that all the remaining positions contain the blank symbol #.
j
+1, in
c
j
.Since
The initial configuration is (
q
0
,
0
,
(#
,
#)). The configuration
c
j
+1
=(
q
j
+1
,
i
j
+1
,
a
j
+1
) is
the successor of the configuration
c
j
=(
q
j
,
i
j
,
a
j
) if the following holds (assuming
a
j
=
(
a
j
,
0
,...,
a
j
,
j
+1
)):
(
q
j
,
a
j
,
i
j
)=(
q
j
+1
,
a
,
d
),
•
δ
a
j
+1
=(
a
j
,
0
,...,
a
j
,
i
j
−
1
,
a
,
a
j
,
i
j
+1
,...,
a
j
,
j
+1
,
#),and
•
•
if
d
=
right
,then
i
j
+1
=
i
j
+1, otherwise
i
j
+1
=
i
j
−
1.
A configuration is halting if it is of the form (
q
,
i
,
a
) for some
q
∈
F
. Thus, a halting
configuration has no successor configuration.
Let
c
=(
c
0
,
c
1
,...,
c
n
) be a computation of
A
. Assume that
c
j
=(
q
j
,
i
j
,
a
j
=
(
a
j
,
0
,...,
a
j
,
j
+1
)) for each 0
,
c
) over a
schema R
t
that contains the binary relation symbol
Steps
and the ternary relation symbols
Positions
,
Config
and
Symbols
. The instance
T
(
≤
j
≤
n
.Werepresent
c
as a target instance
T
(
A
A
,
c
) is defined as follows:
•
,
c
) consists of elements
u
0
,
v
0
,
u
1
,
v
1
,...,
u
n
,
v
n
,
v
n
+1
, where (i)
u
0
and
v
0
are set to be the constant 0 and
v
1
is set to be the constant 1, and (ii)
u
1
,
u
2
,
v
2
,...,
u
n
,
v
n
,
v
n
+1
are distinct elements in
V
AR
. Intuitively,
u
0
,...,
u
n
encode the configuration steps and
v
0
,...,
v
n
+1
encode the
tape positions.
A
,
c
))
A
The
domain
D
OM
(
T
(
of
T
(
•
The interpretation of
Steps
is the successor relation in the set of configuration steps;
namely,
Steps
T
(
A ,
c
)
=
{
(
u
j
,
u
j
+1
)
|
0
≤
j
≤
n
−
1
}
.
•
The interpretation of
Positions
is the successor relation on the set of positions for each
configuration; namely,
Positions
T
(
A ,
c
)
=
{
(
u
j
,
v
,
v
+1
)
|
0
≤
j
≤
n
,
0
≤
≤
j
}
.
