Back to Search
Start Over
There is a deep 1-generic set
- 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.
- Subjects :
- Mathematics - Logic
Computer Science - Logic in Computer Science
03D30, 68Q30
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2409.00631
- Document Type :
- Working Paper