paint-brush

This story draft by @escholar has not been reviewed by an editor, YET.

Bridging Computational Notions of Depth: Appendix A. Proof of Lemma 3

EScholar: Electronic Academic Papers for Scholars HackerNoon profile picture

Authors:

(1) Laurent Bienvenu;

(2) Christopher P. Porter.

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

Appendix A. Proof of Lemma 3

Working towards the proof of Lemma 3, we first establish the following result.



We thus have the identity



Then by our initial assumption on t and t′, we have



The lemma follows by taking the negative logarithm of this inequality


We can now prove Lemma 3. The (i)→(ii) implication is immediate. For the (ii)→(i) implication, suppose X is a sequence and h a computable increasing function such that



for any time bound t. If k ∈ [h(n), h(n + 1)), we have



We now apply the previous lemma with σ = X↾h(n), τ = X↾[h(n), k) and E the map such that, on input ρ, checks whether ρ has length h(n) for some n and if so returns all strings whose length is between 0 and h(n + 1) − h(n) (otherwise E(ρ) is empty). The lemma gives us a computable time bound s such that



This being true for all n and all k ∈ [h(n), h(n + 1)), we have



and thus X is order-deep.


Finally, the (ii)↔(iii) equivalence can be established using Lemma 1(iii) and Theorem 2.


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


L O A D I N G
. . . comments & more!

About Author

EScholar: Electronic Academic Papers for Scholars HackerNoon profile picture
EScholar: Electronic Academic Papers for Scholars@escholar
We publish the best academic work (that's too often lost to peer reviews & the TA's desk) to the global tech community

Topics

Around The Web...