Necessary and sufficient conditions for a Turing degree to be an element of the spectrum of the classical field of computable real numbers are established.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Yu. L. Ershov, Numeration Theory [in Russian], Nauka, Moscow (1977).
S. S. Goncharov and Yu. L. Ershov, Constructive Models, Sib. School Alg. Log. [in Russian], Nauch. Kniga, Novosibirsk (1999).
C. J. Ash and J. F. Knight, Computable Structures and the Hyperarithmetical Hierarchy, Stud. Log. Found. Math., 144, Elsevier, Amsterdam (2000).
G. S. Tsejtin, “Mean value theorems in constructive analysis,” Am. Math. Soc., Translat., II. Ser., 98, 11-40 (1971).
P. Martin-Löf, Notes on Constructive Mathematics, Almqvist and Wiksell, Stockholm (1971).
V. Brattka, “Computable versions of Baire’s category theorem,” in Mathematical Foundations of Computer Science, J. Sgall et al. (Eds.), Lect. Notes Comput. Sci., 2136, Springer, Berlin, (2001), pp. 224-235.
A. Frolov, I. Kalimullin, V. Harizanov, O. Kudinov, and R. Miller, “Spectra of high n and non-low n degrees,” J. Log. Comput., 22, No. 4, 755-777 (2012).
H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967).
K. Weihrauch, Computable Analysis. An Introduction, Texts Theoret. Comput. Sci. EATCS Ser., Springer-Verlag, Berlin (2000).
H. G. Rice, “Recursive real numbers,” Proc. Am. Math. Soc., 5, No. 5, 784-791 (1954).
D. A. Martin, “Classes of recursively enumerated sets and degrees of unsolvability,” Z. Math. Log. Grund. Math., 12, No. 4, 295-310 (1966).
J. R. Shoenfield, Degrees of Unsolvability, North-Holland Math. Stud., 2, Elsevier, New York (1971).
C. G. Jockusch, Jr., “Degrees in which the recursive sets are uniformly recursive,” Can. J. Math., 24, 1092-1099 (1972).
A. Robinson, Introduction to Model Theory and to the Metamathematics of Algebra, North Holland, Amsterdam (1963).
J. Bochnak, M. Coste, and M.-F. Roy, Real Algebraic Geometry, Springer-Verlag, Berlin (1998).
A. Fröhlich and J. Shepherdson, “Effective procedures in field theory,” Philos. Trans. Roy. Soc. London, Ser. A, 248, 407-432 (1956).
Author information
Authors and Affiliations
Corresponding author
Additional information
(M. V. Korovina, O. V. Kudinov) Supported by RFBR (project No. 14-01-00376) and by DFG/RFBR joint grant CAVER BE 1267/14-1 and 14-01-91334.
Translated from Algebra i Logika, Vol. 55, No. 6, pp. 738-759, November-December, 2016.
Rights and permissions
About this article
Cite this article
Korovina, M.V., Kudinov, O.V. Spectrum of the Field of Computable Real Numbers. Algebra Logic 55, 485–500 (2017). https://doi.org/10.1007/s10469-017-9419-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10469-017-9419-8