Bridging Computational Notions of Depth: Members of Deep Classes

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

\

\

\ By Lemma 3, we can conclude that X is order-deep.

\ One immediate consequence of Theorem 9 is the following.

\

\ The converse of this result does not hold.

\

\

\

\

\ As an immediate consequence of Theorem 9 and the above results from [BP16], we have:

\

\

\

\

\ Next, we have:

\

\

\

\

\

:::info This paper is available on arxiv under CC BY 4.0 DEED license.

:::

:::info Authors:

(1) Laurent Bienvenu;

(2) Christopher P. Porter.

:::

\