Graphics Reference
In-Depth Information
If we allowed rational functions in (2), then g
n
may not be defined because its denom-
inator vanishes on s. It turns out that it is easy to overcome this technical problem
and so there is no loss in generality if we assume that g
n
is always defined on any
value where we want to evaluate it.
Definition.
A
computation of length t
is a sequence
(
()
) (
)
=
(
()
) (
)
=
2
(
()
)
(
)
=
t
(
()
)
1
,
i
xns G xns G
,
,
1
,
i
,
,
1
,
i
x
,
K
,
ns G
,
1
,
i
x
,
(5.8)
11
2 2
t
t
where x is an element of I. The set
{
()
}
W
M
=Œ
x
I
there
is a computation of the form 5.8 with n an output node
t
is called the
halting set
of M. The
input-output map
j
MM
O
: WÆ
is defined as follows: Let x ŒW
M
and let (5.8) be the computation with o = n
t
ΠO.
Then
()
=
(
.
j
M
xgs
o
t
Definition.
A map f : A Õ R
m
Æ R
n
is said to be
computable over R
if there exists a
machine M over R so that W
M
= A and j
M
= f. In this case we say that M
computes
f.
Definition.
A set A Õ R
m
is
recursively enumerable
over R if A =W
M
for some machine
M over R. It is
decidable
if it and its complement are both recursively enumerable over
R; otherwise it is said to be
undecidable
.
One can show that decidability of a set A is equivalent to its characteristic func-
tion being computable. Lots of interesting results about machines over a ring are
proved in [BlSS89]. The ones most interesting for us here will now be mentioned.
5.11.3
Theorem.
A recursively enumerable set over R is the countable union of
semialgebraic sets.
Proof.
See [BlSS89].
5.11.4 Corollary.
The halting set of a machine over R is the countable union of
disjoint semialgebraic sets. The input-output map for the machine is a piecewise poly-
nomial map.
Since one can show that the Hausdorff-Besicovitch dimension of a semialgebraic
set is an integer, we also get
5.11.5
Corollary.
The halting set of a machine over R has integral Hausdorff
dimension.
