Nearly computable real numbers
Peter H. Hertling, Philip Janicki · Computability · 2023
We call a sequence [Formula: see text] of elements of a metric space nearly computably Cauchy if for every increasing computable function [Formula: see text] the sequence [Formula: see text] converges computably to 0. We show that there exists an increasing sequence of rational numbers that is nearly computably Cauchy and unbounded. Then we call a real number α nearly computable if there exists a computable sequence [Formula: see text] of rational numbers that converges to α and is nearly computably Cauchy. It is clear that every computable real number is nearly computable, and it follows from a result by Downey and LaForte ( Theoretical Computer Science 284 ( 2002 ) 539–555) that there exists a nearly computable and left-computable number that is not computable. We observe that the set of nearly computable real numbers is a real closed field and closed under computable real functions with open domain, but not closed under arbitrary computable real functions. Among other things we strengthen results by Hoyrup ( Theory of Computing Systems 60 ( 2017 ) 396–420) and by Stephan and Wu (In New computational paradigms. First conference on computability in Europe, CiE 2005, Proceedings ( 2005 ) 461–469 Springer) by showing that any nearly computable real number that is not computable is weakly 1-generic (and, therefore, hyperimmune and not Martin-Löf random) and strongly Kurtz random (and, therefore, not K-trivial), and we strengthen a result by Downey and LaForte ( Theoretical Computer Science 284 ( 2002 ) 539–555) by showing that no promptly simple set can be Turing reducible to a nearly computable real number.