K-trivial, K-low and MLR-low sequences: a tutorial

Abstract : A remarkable achievement in algorithmic randomness and algorithmic information theory was the discovery of the notions of K-trivial, K-low and Martin-Lof-random-low sets: three different definitions turns out to be equivalent for very non-trivial reasons. This paper, based on the course taught by one of the authors (L.B.) in Poncelet laboratory (CNRS, Moscow) in 2014, provides an exposition of the proof of this equivalence and some related results. We assume that the reader is familiar with basic notions of algorithmic information theory.
Type de document :
Chapitre d'ouvrage
Fields of Logic and Computation II, LNCS (9300), Springer, pp.1-23, 2015, Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday, 978-3-319-23533-2. 〈10.1007/978-3-319-23534-9_1〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233787
Contributeur : Alexander Shen <>
Soumis le : mercredi 25 novembre 2015 - 17:41:20
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05

Lien texte intégral

Identifiants

Collections

Citation

Laurent Bienvenu, Alexander Shen. K-trivial, K-low and MLR-low sequences: a tutorial. Fields of Logic and Computation II, LNCS (9300), Springer, pp.1-23, 2015, Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday, 978-3-319-23533-2. 〈10.1007/978-3-319-23534-9_1〉. 〈lirmm-01233787〉

Partager

Métriques

Consultations de la notice

56