Classification of computably approximable real numbers

Hierarchies of computability and definability (03D55) Computation over the reals, computable analysis (03D78) Constructive and recursive analysis (03F60)

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.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Classification of computably approximable real numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1015380)