The Turing Closure of an Archimedean Field.
Paolo Boldi, Sebastiano Vigna · 1998
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 iff they are not Turing closed. Then, the partially ordered set of Turing closed fields is proved isomorphic to the ideal completion of unsolvability degrees. 1 Introduction In a previous paper [2], the authors have introduced a version of the BSS model of computability [1] in which exact tests are not allowed. Essentially, a BSS machine is #-uniform iff its halting set and computed function do not change when the test for equality with 0 is replaced with a test for membership to an arbitrary ball around 0. A set is #-uniformly semi-decidable iff it is the halting set of a #-uniform BSS machine; as it turns out, such sets are always open. There is a strict relation between #-uniform computability and r...