Table of Links
Abstract and 1 Introduction
2 Background
3 On the slow growth law
4 Members of Deep Π0 1 classes
5 Strong depth is Negligible
6 Variants of Strong Depth
References
References
[BDM23] Laurent Bienvenu, Valentino Delle Rose, and Wolfgang Merkle. Relativized depth. Theoretical Computer Science, 949:113694, 2023.
[BDNM15] Laurent Bienvenu, Rodney G. Downey, Andr´e Nies, and Wolfgang Merkle. Solovay functions and their applications in algorithmic randomness. Journal of Computer and System Sciences, 81(8):1575–1591, 2015.
[Ben95] Charles H. Bennett. Logical depth and physical complexity. In The Universal Turing Machine A Half-Century Survey, pages 207–235. Springer, 1995.
[BHPS14] Laurent Bienvenu, Rupert H¨olzl, Christopher P. Porter, and Paul Shafer. Randomness and semi-measures. preprint, arXiv:1310.5133, 2014.
[BP12] Laurent Bienvenu and Christopher P. Porter. Strong reductions in effective randomness. Theoretical Computer Science, 459:55–68, 2012.
[BP16] Laurent Bienvenu and Christopher P Porter. Deep classes. Bulletin of Symbolic Logic, 22(2):249–286, 2016.
[DMN17] Rod Downey, Michael McInerney, and Keng Meng Ng. Lowness and logical depth. Theoretical Computer Science, 702:23–33, 2017.
[HP17] Rupert H¨olzl and Christopher P Porter. Randomness for computable measures and initial segment complexity. Annals of Pure and Applied Logic, 168(4):860–886, 2017.
[JLL94] David W Juedes, James I Lathrop, and Jack H Lutz. Computational depth and reducibility. Theoretical Computer Science, 132(1-2):37–70, 1994.
[Kau91] Steven M. Kautz. Degrees of random sequences. PhD thesis, Cornell University, 1991.
[KHMS11] Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan. Kolmogorov complexity and the recursion theorem. Transactions of the American Mathematical Society, 363(10):5465–5480, 2011.
[Lev73] Leonid A Levin. On the notion of a random sequence. In Soviet. Math. Dokl., volume 14, pages 1413–1416, 1973.
[Lev84] Leonid Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61:15–37, 1984.
[Lev13] Leonid Levin. Forbidden information. Journal of the ACM, 60(2):9, 2013.
[LZ70] L. A. Levin and A. K. Zvonkin. The complexity of finite objects and the basing of the concepts of information and randomness on the theory of algorithms. Uspehi Mat. Nauk, 25(6(156)):85–127, 1970.
[MS17] Philippe Moser and Frank Stephan. Depth, highness and dnr degrees. Discrete Mathematics & Theoretical Computer Science, 19(special issue FCT’15), 2017.
[MSU98] Andrei A Muchnik, Alexei L Semenov, and Vladimir A Uspensky. Mathematical metaphysics of randomness. Theoretical Computer Science, 207(2):263–317, 1998.
[Nie09] Andr´e Nies. Computability and randomness, volume 51. Oxford University Press, 2009.
[SF77] Claus-Peter Schnorr and P Fuchs. General random sequences and learnable sequences. The Journal of Symbolic Logic, 42(3):329–340, 1977.
Appendix A. Proof of Lemma 3
Working towards the proof of Lemma 3, we first establish the following result.
We thus have the identity
Then by our initial assumption on t and t′, we have
The lemma follows by taking the negative logarithm of this inequality
We can now prove Lemma 3. The (i)→(ii) implication is immediate. For the (ii)→(i) implication, suppose X is a sequence and h a computable increasing function such that
for any time bound t. If k ∈ [h(n), h(n + 1)), we have
We now apply the previous lemma with σ = X↾h(n), τ = X↾[h(n), k) and E the map such that, on input ρ, checks whether ρ has length h(n) for some n and if so returns all strings whose length is between 0 and h(n + 1) − h(n) (otherwise E(ρ) is empty). The lemma gives us a computable time bound s such that
This being true for all n and all k ∈ [h(n), h(n + 1)), we have
and thus X is order-deep.
Finally, the (ii)↔(iii) equivalence can be established using Lemma 1(iii) and Theorem 2.
Authors:
(1) Laurent Bienvenu;
(2) Christopher P. Porter.
Photo by Matt Hardy on Unsplash
