|
NeuroCOLT
Technical Report NC-TR-97-019
delta-uniform
BSS Machines
Paolo
Boldi, Sebastiano Vigna
Universita degli Studi di Milano
Italy
Abstract
A $\delta$-uniform BSS machine is a standard BSS machine which does
not rely on exact equality tests. We prove that, for any archimedean
field $R$, a set is $\delta$-uniformly semi-decidable iff it is open
and semi-decidable by a BSS machine which is locally time bounded;
we also prove that the local time bound is nontrivial. This entails
a number of results about BSS machines, in particular the existence
of decidable sets whose interior (closure) is not even semi-decidable
without adding constants. Finally, we show that the sets semi-decidable
by Turing machines are the sets semi-decidable by $\delta$-uniform
machines with coefficients in Q or T, the field of Turing computable
numbers.
Download Compressed
Postscript
Title
Page
|