Random Semicomputable Reals Revisited

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.
Type de document :
Communication dans un congrès
WTCS: Workshop on Theoretical Computer Science, Feb 2012, Auckland, New Zealand. LNCS, pp.031-045, 2012, Computation, Physics and Beyond. 〈http://www.cs.auckland.ac.nz/research/conferences/wtcs2012/〉. 〈10.1007/978-3-642-27654-5〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00845796
Contributeur : Andrei Romashchenko <>
Soumis le : mercredi 17 juillet 2013 - 17:49:22
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05

Identifiants

Collections

Citation

Laurent Bienvenu, Alexander Shen. Random Semicomputable Reals Revisited. WTCS: Workshop on Theoretical Computer Science, Feb 2012, Auckland, New Zealand. LNCS, pp.031-045, 2012, Computation, Physics and Beyond. 〈http://www.cs.auckland.ac.nz/research/conferences/wtcs2012/〉. 〈10.1007/978-3-642-27654-5〉. 〈lirmm-00845796〉

Partager

Métriques

Consultations de la notice

64