|
NeuroCOLT
Technical Report NC-TR-99-052
The
Turing Closure of an Archimedean Field
Paolo
Boldi & Sebastiano Vigna
Università degli Studi di Milano
Received:
21-JAN-2000
Abstract
A BSS machine
is *-uniform if it does not use exact tests; such machines are equivalent
(modulo parameters) to Type 2 Turing machines. We define a notion
of closure related to Turing machines for Archimedean fields, and
show that such fields admit nontrivial *- uniformly decidable sets
if they are not Turing closed. Then, the partially ordered set of
Turing closed fields is proved isomorphic to the ideal completion
of unsolvability degrees.
Download Compressed Postscript
|