Autor:	Shen, Alexander
Rok vydání:	2023
Předmět:	Computer Science - Information Theory Computer Science - Data Structures and Algorithms Mathematics - Logic 94A45 E.4
Druh dokumentu:	Working Paper
Popis:	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 Ku\v{c}era--G\'acs theorem (saying that every sequence is Turing reducible to a random one). Comment: (Added a small remark about non-binary case in v.2)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2304.04852 Zobrazit plný text záznamu View this record from Arxiv