The Kučera–Gács theorem revisited by Levin - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2023

The Kučera–Gács theorem revisited by Levin

Résumé

Leonid Levin (https://arxiv.org/abs/cs/0503039v14) published a new (and very nice) proof of the Kučera–Gács theorem that occupies only a few lines when presented in his style. We try to explain more details and discuss the connection of this proof with image randomness theorems, making explicit some result that is implicit in Levin's paper. Then we review the previous work about the oracle use when reducing a given sequence to another one, and its connection with algorithmic dimension theory.
Fichier principal
Vignette du fichier
2111.00516.pdf (206.09 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-03957655 , version 1 (17-10-2023)

Identifiants

Citer

George Barmpalias, Alexander Shen. The Kučera–Gács theorem revisited by Levin. Theoretical Computer Science, 2023, 947, pp.#113693. ⟨10.1016/j.tcs.2023.113693⟩. ⟨lirmm-03957655⟩
32 Consultations
5 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More