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
Appendix A. Proof of Lemma 3
3. On the Slow Growth Law
In this section, we provide a proof of the slow growth law and provide some hitherto unobserved consequences of the result. In particular, the proof of the slow growth law that we offer here is distinct from others in the literature in two respects. First, unlike other proofs in the literature, such as the one found in [JLL94], which are more complexity-theoretic (using the machinery of Kolmogorov complexity), our proof is measure-theoretic, being based on computable semimeasures. Second, the proof offered here is much more direct than currently available proofs of the slow growth law.
We are now ready to prove our main theorem.
Proof. Define q simply as the push-forward measure of p under F:
We note here some previously unnoticed consequence of slow growth law. First, observe that the standard unsolvable problems from computability theory are strongly deep, including:
Authors:
(1) Laurent Bienvenu;
(2) Christopher P. Porter.
