Premium
Continued fractions of primitive recursive real numbers
Author(s) -
Georgiev Ivan
Publication year - 2015
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201400013
Subject(s) - mathematics , fraction (chemistry) , continued fraction , primitive recursive function , natural number , real number , converse , irrational number , computability , algebraic number , discrete mathematics , computable number , number theory , integer (computer science) , combinatorics , arithmetic , remainder , computable analysis , mathematical analysis , chemistry , geometry , organic chemistry , computer science , programming language
A theorem, proven in the present author's Master's thesis [2][I. Georgiev, 2009] states that a real number isE 2 ‐computable, whenever its continued fraction is inE 2 (the third Grzegorczyk class). The aim of this paper is to settle the matter with the converse of this theorem. It turns out that there exists a real number, which isE 2 ‐computable, but its continued fraction is not primitive recursive, let alone inE 2 . A question arises, whether some other natural condition on the real number can be combined withE 2 ‐computability, so that its continued fraction has low complexity. We give two such conditions. The first is E 2 ‐irrationality, based on a notion of Péter, and the second is polynomial growth of the terms of the continued fraction. Any of these two conditions, combined withE 3 ‐computability gives an E 3 (elementary) continued fraction. We conclude that all irrational algebraic real numbers and the number π have continued fractions inE 3 . All these results are generalized to higher levels of Grzegorczyk's hierarchy as well.