Randomness versus superspeedability

Read full text
Authors: Rupert Hölzl, Philip Janicki, Wolfgang Merkle, Frank Stephan
Cited by: 1
References: 20

Abstract

A real number is left-computable if it can be effectively approximated from below. A real number is speedable if it has such approximations that can be accelerated infinitely often by a constant factor, and it is superspeedable if it is uniformly speedable by arbitrary factors. We answer a question of Barmpalias by separating the speedable and the superspeedable real numbers. The two latter types of real numbers integrate themselves into a hierarchy of subclasses of the left-computable real numbers that has been studied in a growing body of recent work. We add a new perspective to these studies by juxtaposing this hierarchy with the well-studied hierarchy of algorithmic randomness notions and show that there is a superspeedable real number that is Schnorr random.

Fields of Study & Subjects

Evolutionary Algorithms and Applications

Publication details

Journal / source
Information and Computation
Publisher
Elsevier BV
Volume
312
Pages
105505–105505
Publication date
20 August 2026
Language
EN