The Kraft–Barmpalias–Lewis-Pye lemma revisited

Alexander Shen

doi:10.48550/arxiv.2304.04852

Retour

Prépublication

The Kraft–Barmpalias–Lewis-Pye lemma revisited

Alexander Shen

10/04/2023

DOI: https://doi.org/10.48550/arxiv.2304.04852

Résumé

Computer Science - Data Structures and Algorithms

Computer Science - Information Theory

Mathematics - Information Theory

Mathematics - Logic

This note provides a simplified exposition of the proof of hierarchical Kraft lemma proven by Barmpalias and Lewis-Pye and its consequences for the oracle use in the Kucera--Gács theorem (saying that every sequence is Turing reducible to a random one).

Indicateurs

1 Consultations de la notice

Détails

Titre: The Kraft–Barmpalias–Lewis-Pye lemma revisited
Créateurs - sans rôle: Alexander Shen
Identifiants: 99157042909311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Langue: English
Type de ressource: Preprint