Bridging Computational Notions of Depth: How We Studied the Relationship

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

1. Introduction

Bennett established several fundamental facts about strongly deep sequences, namely that the halting set K is strongly deep, that no computable sequence and no Martin-L¨of random sequence is strongly deep, and that strong depth is closed upwards under truth-table reducibility (a result he referred to as the slow growth law). Bennett further introduced the notion of weak depth, where a sequence is weakly deep if it is not truth-table reducible to a random sequence.

One takeaway we aim to emphasize in this study is the importance of the slow growth law for the study of depth, akin to the role of randomness preservation in the study of algorithmic randomness. According to the latter, every sequence that is truth-table reducible to a sequence that is random with respect to a computable measure is itself random with respect to a computable measure, which is precisely the dual of the slow growth law for deep sequences. We anticipate that the slow growth law will continue to be a useful tool in the study of notions of depth.