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.
No takes yet. Share an insight, caveat, or question.
Ang Li (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: