We consider various ways to represent irrational numbers by subrecursive functions. An irrational number can be represented by its base-b expansion; by its base-b sum approximation from below; and by its base-b sum approximation from above. Let be a class of subrecursive functions, e.g., the class the primitive recursive functions. The set of irrational numbers that can be obtained by functions from depends on the representation and the base b. We compare the sets obtained by different representations and bases. We also discuss how representations by base-b expansions and sum approximations relate to representations by Cauchy sequences and Dedekind cuts.
O.Aberth, Computable Analysis, MacGraw-Hill, New York, 1980.
2.
S.B.Cooper, Computability Theory, Chapman and Hall/CRC, Boca Raton, FL2003.
3.
I.Georgiev, Continued fractions of primitive recursive real numbers, Mathematical Logic Quarterly61(4–5) (2015), 288–306. doi:10.1002/malq.201400013.
4.
K.Ko, On the definitions of some complexity classes of real numbers, Mathematical Systems Theory16 (1983), 95–109. doi:10.1007/BF01744572.
5.
K.Ko, On the continued fraction representation of computable real numbers, Theoretical Computer Science47 (1986), 299–313. doi:10.1016/0304-3975(86)90154-4.
6.
L.Kristiansen, Information content and computational complexity of recursive sets, in: Gödel ’96, P.Hajek, ed., Springer Lecture Notes in Logic, Vol. 6, Springer-Verlag, Heidelberg, 1996, pp. 235–246.
7.
L.Kristiansen, Papers on subrecursion theory, Dr Scient Thesis, Research Report 217, Department of Informatics, University of Oslo, 1996. ISSN 0806-3036, ISBN 82-7368-130-0.
8.
L.Kristiansen, On subrecursive representability of irrational numbers, Computability6 (2017), 249–276. doi:10.3233/COM-160063.
9.
L.Kristiansen, R.Lubarsky, J.-C.Schlage-Puchta and A.Weiermann, On the structure of honest elementary degrees, in: The Infinity Project, S.Friedman, M.Koerwinen and M.Müller, eds, CRM Documents, Vol. 11, CRM (Centre de Recerca Matematica), Bellaterra (Barcelona), 2012, pp. 255–279.
10.
L.Kristiansen, J.-C.Schlage-Puchta and A.Weiermann, Streamlined subrecursive degree theory, Annals of Pure and Applied Logic163 (2012), 698–716. doi:10.1016/j.apal.2011.11.004.
11.
S.Labhalla and H.Lombardi, Real numbers, continued fractions and complexity classes, Annals of Pure and Applied Logic50 (1990), 1–28. doi:10.1016/0168-0072(90)90052-4.
12.
C.Leary and L.Kristiansen, A Friendly Introduction to Mathematical Logic, 2nd edn, Milne Library, SUNY Geneseo, Geneseo, NY, 2015.
13.
R.S.Lehman, On primitive recursive real numbers, Fundamenta Mathematica49 (1961), 105–118. doi:10.4064/fm-49-2-105-118.
R.Péter, Rekursive Funktionen, Verlag der Ungarischen Akademie der Wissenschaften, Budapest, 1957, English translation: Academic Press, New York, 1967.
16.
H.E.Rose, Subrecursion. Functions and Hierarchies, Clarendon Press, Oxford, 1984.
D.Skordev, A.Weiermann and I.Georgiev, -computable real numbers, Journal of Logic and Computation22 (2008), 899–925. doi:10.1093/logcom/exq050.
19.
E.Specker, Nicht Konstruktiv Beweisbare Satze Der Analysis, Journal of Symbolic Logic14 (1949), 145–158. doi:10.2307/2267043.
20.
K.Weihrauch, The degrees of discontinuity of some translators between representations of real numbers, Informatik Berichte 129, Fern Universität Hagen, 1992.
