Real numbers, continued fractions and complexity classes

Annals of Pure and Applied Logic 50 (1):1-28 (1990)
  Copy   BIBTEX

Abstract

We study some representations of real numbers. We compare these representations, on the one hand from the viewpoint of recursive functionals, and of complexity on the other hand.The impossibility of obtaining some functions as recursive functionals is, in general, easy. This impossibility may often be explicited in terms of complexity: - existence of a sequence of low complexity whose image is not a recursive sequence, - existence of objects of low complexity but whose images have arbitrarily high time- complexity .Moreover, some representations of real numbers that are equivalent from the viewpoint of recursive functionals, are very distinct from the viewpoint of complexity.We make a particular study of representations via continued fractions . We precise exactly what part of information available in the x's dfc is equivalent to the information available in its Dedekinds cut. We show that the sum of two reals whose dfcs are polynomial-time computable may be a real whose dfc has time complexity arbitrarily high.This work confirms that the unique representation of real numbers suitable for the ordinary calculus is via explicit Cauchy sequences of rationals.RésuméNous étudions différentes manières de présenter les nombres réels. Nous comparons ces présentations du point de vue des fonctionnelles récursives d'une part, et de celui des classes de complexité d'autre part.L'impossibilité d'obtenir certaines fonctions sous forme de fonctionnelles récursives est en général facile à établir. Cette impossiblité peut souvent être explicitée en termes de complexité: - il existe une suite de faible complexité dont l'image est une suite non récursive, - il existe des objets de faible complexité mais dont les images sont des objets de complexité arbitrairement grande .En outre, certaines présentations des réels équivalentes du point de vue des fonctionnelles récursives se distinguent nettement du point de vue de la complexité.Nous faisons une étude particulière concernant les développements en fraction continue . Nous précisions exactement quelle est la partie de l'information disponible dans le dfc d'un réel x qui équivaut à l'information disponible dans sa coupure de Dedekind. Nous montrons également que la somme de deux réels dont le dfc est calculable en temps polynomial peut être un réel dont le dfc est de complexité arbitrairement grande.Ce travail confirme que seule une présentation des réels via des suites de rationnels explicitement de Cauchy est adaptée aux calculs avec les réels

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,322

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Logics which capture complexity classes over the reals.Felipe Cucker & Klaus Meer - 1999 - Journal of Symbolic Logic 64 (1):363-390.
Complexity analysis for a Hall theorem on continuous fractions.S. Labhalla & H. Lombardi - 1996 - Mathematical Logic Quarterly 42 (1):134-144.
Primitive recursive real numbers.Qingliang Chen, Kaile Kaile & Xizhong Zheng - 2007 - Mathematical Logic Quarterly 53 (4):365-380.
Order‐free Recursion on the Real Numbers.Vasco Brattka - 1997 - Mathematical Logic Quarterly 43 (2):216-234.
Primitive recursive real numbers.Qingliang Chen, Kaile Su & Xizhong Zheng - 2007 - Mathematical Logic Quarterly 53 (4‐5):365-380.
On virtual classes and real numbers.R. M. Martin - 1950 - Journal of Symbolic Logic 15 (2):131-134.
Fibonacci and Continued Fractions.T. E. Phipps Jr - 2008 - Apeiron: Studies in Infinite Nature 15 (4):534.
The isomorphism problem for classes of computable fields.Wesley Calvert - 2004 - Archive for Mathematical Logic 43 (3):327-336.

Analytics

Added to PP
2014-01-16

Downloads
16 (#875,539)

6 months
6 (#506,019)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

References found in this work

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Nicht konstruktiv beweisbare sätze der analysis.Ernst Specker - 1949 - Journal of Symbolic Logic 14 (3):145-158.
Recursive Real Numbers.Norman Shapiro - 1955 - Journal of Symbolic Logic 20 (2):177-177.

Add more references