This content originally appeared on HackerNoon and was authored by Computational Technology for All
Table of Links
4 Members of Deep Π0 1 classes
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.
\
:::info This paper is available on arxiv under CC BY 4.0 DEED license.
:::
:::info Authors:
(1) Laurent Bienvenu;
(2) Christopher P. Porter.
:::
Photo by Matt Hardy on Unsplash
This content originally appeared on HackerNoon and was authored by Computational Technology for All
Computational Technology for All | Sciencx (2025-01-18T03:15:00+00:00) Bridging Computational Notions of Depth: Working Towards the Proof of Lemma 3. Retrieved from https://www.scien.cx/2025/01/18/bridging-computational-notions-of-depth-working-towards-the-proof-of-lemma-3/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.