Random semicomputable reals revisited

DOI10.1007/978-3-642-27654-5_3MaRDI QIDQ2891300zbMATH OpenOpenAlexWikidataFDO

Authors Laurent Bienvenu, A. Shen

Publication date 15 June 2012

Published in Computation, Physics and Beyond (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.5028

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78)

Abstract: The aim of this expository paper is to present a nice series of results, obtained in the papers of Chaitin (1976), Solovay (1975), Calude et al. (1998), Kucera and Slaman (2001). This joint effort led to a full characterization of lower semicomputable random reals, both as those that can be expressed as a "Chaitin Omega" and those that are maximal for the Solovay reducibility. The original proofs were somewhat involved; in this paper, we present these results in an elementary way, in particular requiring only basic knowledge of algorithmic randomness. We add also several simple observations relating lower semicomputable random reals and busy beaver functions.

Recommendations

• A characterization of c. e. random reals
• Computing a Glimpse of Randomness
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• scientific article; zbMATH DE number 1136091
• Randomness, computability, and density

Cites work

• Forbidden information
• scientific article; zbMATH DE number 1136091 (Why is no real title available?)
• Information-theoretic characterizations of recursive infinite strings
• Kolmogorov complexity and solovay functions
• Randomness and recursive enumerability
• Time-Bounded Kolmogorov Complexity and Solovay Functions

Cited in

(8)

• On the Reals Which Cannot Be Random
• Busy beavers and Kolmogorov complexity
• Relative randomness and real closed fields
• What percentage of programs halt?
• scientific article; zbMATH DE number 3943806 (Why is no real title available?)
• Solovay functions and their applications in algorithmic randomness
• SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS
• Random reals and possibly infinite computations Part I: Randomness in ∅′

This page was built for publication: Random semicomputable reals revisited

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