Here's Proof of the Slow Growth Law and Some Unobserved Consequences

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: