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.
The Turing closure of an Archimedean field / P. Boldi, S. Vigna. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 231:2(2000), pp. 143-156.
The Turing closure of an Archimedean field
P. BoldiPrimo
;S. VignaUltimo
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 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.
Pubblicazioni consigliate
I metadati presenti in AIR sono rilasciati con licenza CCO mentre i file delle pubblicazioni sono rilasciati con licenza CC BY-SA, salvo diversa indicazione. In caso di violazione di copyright, contattare l'assistenza di AIR
