Bridging Computational Notions of Depth: Working Towards the Proof of Lemma 3

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.

Photo by Matt Hardy on Unsplash