arXiv Analytics

Sign in

arXiv:2409.00631 [math.LO]AbstractReferencesReviewsResources

There is a deep 1-generic set

Ang Li

Published 2024-09-01Version 1

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.

Categories: math.LO, cs.LO
Subjects: 03D30, 68Q30
Related articles: Most relevant | Search more
arXiv:1210.4937 [math.LO] (Published 2012-10-17, updated 2013-03-20)
From Bi-immunity to Absolute Undecidability
arXiv:1405.5139 [math.LO] (Published 2014-05-20, updated 2017-04-12)
Algorithmic identification of probabilities is hard
arXiv:1304.0999 [math.LO] (Published 2013-04-03, updated 2015-02-08)
On commutative weak BCK-algebras

Links

Toolbox