Bridging Computational Notions of Depth: Here's Why Strong Depth is Negligible

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

\ Theorem 25. The class of strongly deep sequences is negligible.

\ Proof. For the sake of contradiction, assume there exists a functional Φ such that

\

\ It is clear that q is computable. Moveover, q is a discrete semimeasure, since

\

\

\ On the other hand, for almost all n:

\

\ Note, by contrast, that the collection of weakly deep sequences is not negligible. Indeed, as shown by Muchnik et al. [MSU98], no 1-generic sequence is Martin-L¨of random with respect to a computable measure, and thus every 1-generic is weakly deep. Moreover, as shown by Kautz [Kau91], every 2-random sequence computes a 1-generic, and hence the collection of 1-generics is not negligible.

\

\

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

:::

:::info Authors:

(1) Laurent Bienvenu;

(2) Christopher P. Porter.

:::

\