Database Reference
In-Depth Information
PROBLEM
: U
NI
S
OL
E
XISTENCE
M
.
INPUT:
A source instance
S
.
QUESTION
:
Is there a universal solution for
S
under
M
?
Like the existence of solutions, this problem is undecidable for arbitrary relational map-
pings.
Theorem 6.5
There exists a relational mapping
M
=(R
s
,
R
t
,
Σ
st
,
Σ
t
)
, such that the prob-
lem
U
NI
S
OL
E
XISTENCE
M
is undecidable.
Note that
Theorem 6.5
does
not
follow from (the proof of)
Theorem 5.3
, that is, from
the undecidability of the problem of existence of solutions. Indeed, it is easy to see that for
the mapping
used in that proof, the existence of solutions does not necessarily coincide
with the existence of universal solutions. Nor does
Theorem 5.3
follow from the proof of
Theorem 6.5
. This is because for the mapping
M
that we construct in the proof below, the
problem of existence of solutions is trivial, as every source instance has a solution.
M
Proof of
Theorem 6.5
This time we provide a generic reduction from the halting problem
for single-tape deterministic Turing machines that never move their head to the left of the
initial position. In particular, this means that we can assume without loss of generality that
the tape is infinite only to the right. Clearly, the halting problem for this class of Turing
machines is undecidable. We construct a mapping
such that source instances encode
Turing machines and universal solutions encode halting computations of Turing machines
on the empty input.
Let
M
,
q
0
,
F
) be a single-tape deterministic Turing machine that never moves
its head to the left of the initial position, where:
A
=(
Q
,
A
,
δ
•
Q
is a finite set of states,
•
A
is the tape alphabet that contains a distinguished blank symbol that we denote by #,
•
δ
: (
Q
\
F
)
×
A
→
Q
×
A
×{
left
,
right
}
is the (total) transition function,
•
q
0
∈
Q
is the initial state,
•
⊆
and
F
Q
is the set of final states.
Notice that we assume without loss of generality that final states are terminal, i.e.
when the machine enters an accepting state it halts, and that
those are the only
halting states. We encode
A
as an instance
S
(
A
) over the source schema R
s
=
{
Δ
,
Init
,
Zero
,
One
,
Blank
,
Left
,
Right
}
,where
Δ
is a 5-ary relation symbol and the rest of
the symbols in R
s
are unary. We define
S
(
A
) as follows:
S
(
A
)
consists of all the tuples (
q
,
a
,
q
,
a
,
d
) (
q
,
q
∈
Q
,
a
,
a
∈
•
Δ
A
,
d
∈{
left
,
right
}
)such
(
q
,
a
)=(
q
,
a
,
d
);thatis,
S
(
A
)
encodes the transition graph of
that
δ
Δ
δ
.
Init
S
(
A
)
contains only the initial state
q
0
.
•
Zero
S
(
A
)
contains only the constant 0,
One
S
(
A
)
contains only the constant 1,
Blank
S
(
A
)
contains only the symbol #,
Left
S
(
A
)
contains only the direction
left
, and, finally,
Right
S
(
A
)
contains only the direction
right
.
•
