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 5. Strong Depth is Negligible 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. This paper is available on arxiv under CC BY 4.0 DEED license. Authors:
(1) Laurent Bienvenu;
(2) Christopher P. Porter. Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Background 2 Background 3 On the slow growth law 3 On the slow growth law 4 Members of Deep Π0 1 classes 4 Members of Deep Π0 1 classes 5 Strong depth is Negligible 5 Strong depth is Negligible 6 Variants of Strong Depth 6 Variants of Strong Depth References References Appendix A. Proof of Lemma 3 Appendix A. Proof of Lemma 3 5. Strong Depth is Negligible Theorem 25. The class of strongly deep sequences is negligible. 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 q q On the other hand, for almost all n : 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. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv Authors: (1) Laurent Bienvenu; (2) Christopher P. Porter. Authors: Authors: (1) Laurent Bienvenu; (2) Christopher P. Porter.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

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

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Data-centric Approach to Class-specific Bias in Image Data Augmentation: Abstract and Intro

Bank Discount.

Beneath this mask is Data — Part 1 (or how to make lemonade)

Calculating the Square Root of a Number using the Newton-Raphson Method [A How To Guide]

Effective Parallel Computing

Equation of Payments.

A Data-centric Approach to Class-specific Bias in Image Data Augmentation: Abstract and Intro

Bank Discount.

Beneath this mask is Data — Part 1 (or how to make lemonade)

Calculating the Square Root of a Number using the Newton-Raphson Method [A How To Guide]

Effective Parallel Computing

Equation of Payments.

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps