Bridging Computational Notions of Depth: Turing Functionals, Semimeasures, and More

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

2. Background

Lemma 1 ([BDM23]).

In addition, we need the following theorem (see, e.g. [JLL94, Theorem 4.3(2)]).

Note that by combining Lemma 1(iii) and Theorem 2, we obtain a resource-bounded analogue of Levin’s coding theorem.

In the rest of the paper we will sometimes use an equivalent characterization of order-depth, given by the following lemma.

The proof of this lemma is technical; for the sake of readability, we defer it to the appendix.

The slow growth law also holds for order-depth.