Classification of computably approximable real numbers
type: Item
instance of: scholarly article
title: Classification of computably approximable real numbers
zbMATH Open document ID: 1176.03020
published in: Theory of Computing Systems
publication date: 2009-05-08T00:00:00Z
review text: The notion of a \(k\)-effectively computable real is introduced. This can be defined as follows: a real \(x\) is \(k\)-effectively computable if there is a computable sequence of rational numbers \(\{x_s\}_{s\in\mathbb{N}}\) that converges to \(x\) and such that for almost all \(n\), the number of non-overlapping intervals \((s,t)\) such that \(s,t\geq n\) and \(|x_s-x_t|>2^{-n}\) is at most \(k\). The class of \(k\)-effectively computable reals is denoted \(k\)-\textbf{EC}. The union of all these classes is denoted \textbf{BEC}, which is short for ``bounded effectively computable''. Clearly, any \(k\)-effectively computable real is \((k+1)\)-effectively computable. It is shown that this hierarchy does not collapse. It is furthermore shown that \textbf{BEC} is a proper subset of the class of weakly computable reals (see e.g. [\textit{K. Ambos-Spies, K. Weihrauch} and \textit{X. Zheng}, J. Complexity 16, No. 4, 676--690 (2000; Zbl 0974.03054)]). It is also shown that there is a 1-effectively computable real that is neither left nor right computable and that there is a c.e. real that is not in \textbf{BEC}. The proofs are all finite-injury priority arguments. This hierarchy can thus be considered a parallel of the finite levels of the Ershov hierarchy [\textit{Yu. L. Ershov}, Algebra Logic 7, 25--43 (1968), English translation from Algebra Logika 7, No.~1, 47--74 (1968; Zbl 0216.00901); Algebra Logic 7, 212--232 (1968), English translation from Algebra Logika 7, No.~4, 15--47 (1968; Zbl 0216.00902); Algebra Logic 9, 20--31 (1970), English translation from Algebra Logika 9, 34--51 (1970; Zbl 0233.02017)]. Variations on the notion of \(k\)-effectively computability are considered wherein \(k\) is replaced by a function \(f\) or by a class of functions \(C\). It is shown that when \(C\) contains the constant functions and is closed under composition, then the class of \(C\)-effectively computable reals is a field.
Mathematics Subject Classification ID: 03D78
Mathematics Subject Classification ID: 03D55
Mathematics Subject Classification ID: 03F60
zbMATH DE Number: 5552170
zbMATH Keywords: computability
zbMATH Keywords: computable real numbers
zbMATH Keywords: computably approximable real numbers
zbMATH Keywords: hierarchy
author: Xizhong Zheng
reviewed by: Timothy H. McNicholl
MaRDI profile type: Publication
full work available at URL: s00224-007-9026-5
OpenAlex ID: W1999739638
cites work: Computable calculus. With 1 CD-ROM (Windows 95, 98, 2000, Windows NT)
cites work: Weakly computable real numbers
cites work: Constructive mathematics: a foundation for computable analysis
cites work: Recursively enumerable reals and Chaitin \(\Omega\) numbers
cites work: Q5316387
cites work: Q5619076
cites work: TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
cites work: Q5824357
cites work: Q4002474
cites work: A General Framework for Priority Arguments
cites work: Q3232283
cites work: Criteria of constructibility for real numbers
cites work: Q3994907
cites work: Q4551395
cites work: Recursive Real Numbers
cites work: Cohesive sets and recursively enumerable Dedekind cuts
cites work: Q3819052
cites work: Nicht konstruktiv beweisbare Sätze der Analysis
cites work: On Computable Numbers, with an Application to the Entscheidungsproblem
cites work: Q4485693
cites work: Weak computability and representation of reals
cites work: Closure properties of real number classes under CBV functions
cites work: Divergence bounded computable real numbers
DOI: 10.1007/S00224-007-9026-5
description: scientific article; zbMATH DE number 5552170