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. This paper is available on arxiv under CC BY 4.0 DEED license. Authors:
(1) Laurent Bienvenu;
(2) Christopher P. Porter. Photo by Matt Hardy on Unsplash Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Background 2 Background 3 On the slow growth law 3 On the slow growth law 4 Members of Deep Π0 1 classes 4 Members of Deep Π0 1 classes 5 Strong depth is Negligible 5 Strong depth is Negligible 6 Variants of Strong Depth 6 Variants of Strong Depth References 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 n k ∈ h n h n and thus X is order-deep. X Finally, the (ii)↔(iii) equivalence can be established using Lemma 1(iii) and Theorem 2. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv Authors: (1) Laurent Bienvenu; (2) Christopher P. Porter. Authors: Authors: (1) Laurent Bienvenu; (2) Christopher P. Porter. Photo by Matt Hardy on Unsplash Matt Hardy Unsplash

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

New Framework Makes Scientific Computing Workflows Truly Reproducible

Bridging Computational Notions of Depth: Variants of Strong Depth

Computational.TECH

Too Long; Didn't Read

Boost your HackerNoon story @ $159.99! 🚀

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Data-centric Approach to Class-specific Bias in Image Data Augmentation: Abstract and Intro

Bank Discount.

Beneath this mask is Data — Part 1 (or how to make lemonade)

Calculating the Square Root of a Number using the Newton-Raphson Method [A How To Guide]

Effective Parallel Computing

A Data-centric Approach to Class-specific Bias in Image Data Augmentation: Abstract and Intro

Bank Discount.

Beneath this mask is Data — Part 1 (or how to make lemonade)

Calculating the Square Root of a Number using the Newton-Raphson Method [A How To Guide]

Effective Parallel Computing

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps