Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Classification of computably approximable real numbers
Zheng X. Theory of Computing Systems43 (3):603-624,2008.Type:Article
Date Reviewed: Jul 21 2009

Real numbers can be represented mathematically in several equivalent ways, but these representations are not equivalent when they are used to compute real numbers and real functions. Although all representations yield computable real numbers, some do not yield computable real functions. Moreover, some real numbers are computable and others are computably approximable. Distinguishing among classes of effectively computable numbers based on the functions used to generate them is the chief contribution of this paper.

After discussing representations of real numbers and real functions, Zheng states the main goal of the paper--classifying the computably approximable real numbers according to the convergence speeds of rational sequences. He fulfills this goal by defining effectively computable numbers in terms of the divergence degree of sequences of rational numbers, classes of effectively computable numbers, and a hierarchy among them. He rounds out the paper by detailing the relationships among these classes.

In the process of fulfilling the goal, Zheng presents and proves a half-dozen or so theorems and lemmas that provide the reader with a detailed and comprehensive treatment of this important aspect of computability. For example, he proves that for any natural number k, there is a k = 1 effectively computable real number that is not effectively computable for k, and that there is a strongly computably enumerable real number that is not effectively computable for any constant.

The paper will be of interest to researchers studying the computability of real numbers and real functions, as well as their implementations.

Reviewer:  Marlin Thomas Review #: CR137123 (0911-1058)
Bookmark and Share
  Featured Reviewer  
 
Multiple Precision Arithmetic (G.1.0 ... )
 
 
Counting Problems (G.2.1 ... )
 
 
Number-Theoretic Computations (F.2.1 ... )
 
 
Numerical Algorithms (G.1.0 ... )
 
 
Combinatorics (G.2.1 )
 
 
General (G.1.0 )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Multiple Precision Arithmetic": Date
 Standardization and testing of implementations of mathematical functions in floating point numbers
Kuliamin V. Programming and Computing Software 33(3): 154-173, 2007. Type: Article
Oct 26 2007

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy