Back to Search Start Over

There is a deep 1-generic set

Authors :
Li, Ang
Publication Year :
2024

Abstract

An infinite binary sequence is Bennett deep if, for any computable time bound, the difference between the time-bounded prefix-free Kolmogorov complexity and the prefix-free Kolmogorov complexity of its initial segments is eventually unbounded. It is known that weakly 2-generic sets are shallow, i.e. not deep. In this paper, we show that there is a deep 1-generic set.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2409.00631
Document Type :
Working Paper