View in EDS

Speedability of computably approximable reals and their approximations.

Saved in:
Bibliographic Details
Title: Speedability of computably approximable reals and their approximations.
Authors: Barmpalias, George1 (AUTHOR) barmpalias@gmail.com, Fang, Nan1 (AUTHOR) fangnan@ios.ac.cn, Merkle, Wolfgang2 (AUTHOR) merkle@math.uni-heidelberg.de, Titov, Ivan2,3 (AUTHOR) me@ivantitov.de
Source: Information & Computation. Jun2026, Vol. 311, pN.PAG-N.PAG. 1p.
Subjects: Real numbers, Algorithmic randomness, Recursion theory
Abstract: 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 { a s } s ∈ ω is speedable if there exists a nondecreasing computable function f such that the approximation { a f (s) } s ∈ ω converges in a certain formal sense faster than { a s } 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. [ABSTRACT FROM AUTHOR]
Copyright of Information & Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 194449742
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Speedability of computably approximable reals and their approximations.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Barmpalias%2C+George%22">Barmpalias, George</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> barmpalias@gmail.com</i><br /><searchLink fieldCode="AR" term="%22Fang%2C+Nan%22">Fang, Nan</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> fangnan@ios.ac.cn</i><br /><searchLink fieldCode="AR" term="%22Merkle%2C+Wolfgang%22">Merkle, Wolfgang</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> merkle@math.uni-heidelberg.de</i><br /><searchLink fieldCode="AR" term="%22Titov%2C+Ivan%22">Titov, Ivan</searchLink><relatesTo>2,3</relatesTo> (AUTHOR)<i> me@ivantitov.de</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Information+%26+Computation%22">Information & Computation</searchLink>. Jun2026, Vol. 311, pN.PAG-N.PAG. 1p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Real+numbers%22">Real numbers</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithmic+randomness%22">Algorithmic randomness</searchLink><br /><searchLink fieldCode="DE" term="%22Recursion+theory%22">Recursion theory</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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 { a s } s ∈ ω is speedable if there exists a nondecreasing computable function f such that the approximation { a f (s) } s ∈ ω converges in a certain formal sense faster than { a s } 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. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Information & Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=194449742
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.ic.2026.105451
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 1
        StartPage: N.PAG
    Subjects:
      – SubjectFull: Real numbers
        Type: general
      – SubjectFull: Algorithmic randomness
        Type: general
      – SubjectFull: Recursion theory
        Type: general
    Titles:
      – TitleFull: Speedability of computably approximable reals and their approximations.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Barmpalias, George
      – PersonEntity:
          Name:
            NameFull: Fang, Nan
      – PersonEntity:
          Name:
            NameFull: Merkle, Wolfgang
      – PersonEntity:
          Name:
            NameFull: Titov, Ivan
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 06
              Text: Jun2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 08905401
          Numbering:
            – Type: volume
              Value: 311
          Titles:
            – TitleFull: Information & Computation
              Type: main
ResultId 1