Speedability of computably approximable reals and their approximations
An approximation of a real is a sequence of rational numbers that converges to the real. An approximation is left-c.e. if it is computable and nondecreasing and is d.c.e. if it is computable and has bounded variation. A real is computably approximable if it has some computable approximation, and lef...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
June 2026
|
| In: |
Information and computation
Year: 2026, Volume: 311, Pages: 1-11 |
| ISSN: | 1090-2651 |
| DOI: | 10.1016/j.ic.2026.105451 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1016/j.ic.2026.105451 Verlag, lizenzpflichtig, Volltext: https://www.sciencedirect.com/science/article/pii/S0890540126000489 
|
| Author Notes: | George Barmpalias, Nan Fang, Wolfgang Merkle, Ivan Titov |
| Summary: | An approximation of a real is a sequence of rational numbers that converges to the real. An approximation is left-c.e. if it is computable and nondecreasing and is d.c.e. if it is computable and has bounded variation. A real is computably approximable if it has some computable approximation, and left-c.e. and d.c.e. reals are defined accordingly. An approximation {as}s∈ω is speedable if there exists a nondecreasing computable function f such that the approximation {af(s)}s∈ω converges in a certain formal sense faster than {as}s∈ω. This leads to various notions of speedability for reals, e.g., one may require for a computably approximable real that either all or some of its approximations of a specific type are speedable. Merkle and Titov established the equivalence of several speedability notions for left-c.e. reals that are defined in terms of left-c.e. approximations. We extend these results to d.c.e. reals and d.c.e. approximations, and we prove that in this setting, being speedable is equivalent to not being Martin-Löf random. Finally, we demonstrate that every computably approximable real has a computable approximation that is speedable. |
|---|---|
| Item Description: | Online verfügbar: 12. April 2026, Artikelversion: 17. April 2026 Gesehen am 10.06.2026 |
| Physical Description: | Online Resource |
| ISSN: | 1090-2651 |
| DOI: | 10.1016/j.ic.2026.105451 |