On the computability of ordered fields

M. V. Korovina ; O. V. Kudinov

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 20 (2023) no. 2, pp. 1341-1360.

Résumé

In this paper we develop general techniques for structures of computable real numbers generated by classes of total computable (recursive) functions with special requirements on basic operations in order to investigate the following problems: whether a generated structure is a real closed field and whether there exists a computable copy of a generated structure. We prove a series of theorems that lead to the result that there are no computable copies for $\mathcal{E}^n$-computable real numbers, where $\mathcal{E}^n$ is a level in Grzegorczyk hierarchy, $n\geq 3$. We also propose a criterion of computable presentability of an archimedean ordered field.

Détail

Keywords: computable analysis, computability, index set, computable model theory, complexity.

Bibliographie

[1] P.E. Alaev, “Computable homogeneous Boolean algebras and a metatheorem”, Algebra Logic, 43:2 (2004), 73–87 | DOI | MR | Zbl

[2] M.M. Arslanov, Local theory of degrees of unsolvability and $\Delta^0_2$-sets, Kazan' University Press, Kazan', 1987 | MR | Zbl

[3] M.M. Arslanov, “On some generalisations of a fixed point theorem”, Sov. Math., 25:5 (1981), 1–10 | MR | Zbl

[4] A. Cobham, “The intrinsic computational difficulty of functions”, Logic, Methodology and Philosophy of Science, Proceedings of the 1964 International Congress, ed. Y. Bar-Hillel, North Holland, Amsterdam, 1964, 24–30 | MR

[5] Yu.L. Ershov, Decision problems and constructivizable models, Nauka, M., 1980 | MR | Zbl

[6] Yu.L. Ershov, “Theory of numberings”, Handbook of computability theory, ed. E.R. Griffor, Elsevier, Amsterdam, 1999, 473–503 | DOI | MR | Zbl

[7] Yu.L. Ershov, S.S. Goncharov, Constructive models, Consultants Bureau, New York, 2000 | MR | Zbl

[8] S.S. Goncharov, Countable Boolean algebras and decidability, Plenum, New York, 1997 | MR | Zbl

[9] A. Grzegorczyk, Some classes of recursive functions, Rozprawy Mathemaczne IV, Warszawa, 1953 | MR | Zbl

[10] N. Khisamiev, “Constructive abelian groups”, Handbook of recursive mathematics, v. 2, Stud. Logic Found. Math., 139, eds. Ershov Yu. L. et al., Elsevier, Amsterdam, 1998, 1177–1231 | DOI | MR | Zbl

[11] Ker-I, Ko, Complexity theory of real functions, Birkhäuser, Boston etc., 1991 | MR | Zbl

[12] M. Korovina, O. Kudinov, “Spectrum of the field of computable real numbers”, Algebra Logic, 55:6 (2017), 485–500 | DOI | MR | Zbl

[13] M. Korovina, O. Kudinov, “The uniformity principle for $\Sigma$-definability”, J. Log. Comput., 19:1 (2009), 159–174 | DOI | MR | Zbl

[14] A.I. Mal'cev, “Constructive algebras”, Russ. Math. Surv., 16:3 (1961), 77–129 | DOI | Zbl

[15] M. Miller, V. Ocasio González, “Degree spectra of real closed fields”, Arch. Math. Logic, 58:3-4 (2019), 387–411 | DOI | MR | Zbl

[16] A.S. Morozov, “Countable homogeneous Boolean algebras”, Algebra Logic, 21 (1983), 181–190 | DOI | MR | Zbl

[17] M.O. Rabin, “Computable algebra, general theory and theory of computable fields”, Trans. Am. Math. Soc., 95:2 (1960), 341–360 | MR | Zbl

[18] R.W. Ritchie, “Classes of predictably computable functions”, Trans. Am. Math. Soc., 106 (1963), 139–173 | DOI | MR | Zbl

[19] H. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, Maidenhead, Berksh, 1967 | MR | Zbl

[20] J.R. Shoenfield, Degrees of unsolvability, North-Holland Publ., Amsterdam-London, 1971 | MR | Zbl

[21] R.M. Smullyan, Theory of formal systems, Annals of Mathematics Studies, 47, Princeton University Press, Princeton, 1961 | MR | Zbl

[22] R.I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Springer, Berlin etc, 1987 | MR | Zbl

[23] K. Weihrauch, Computable analysis. An introduction, Springer, Berlin, 2000 | MR | Zbl