This content originally appeared on HackerNoon and was authored by Computational Technology for All
Table of Links
4 Members of Deep Π0 1 classes
\
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.
\
\
:::info This paper is available on arxiv under CC BY 4.0 DEED license.
:::
:::info Authors:
(1) Laurent Bienvenu;
(2) Christopher P. Porter.
:::
\
This content originally appeared on HackerNoon and was authored by Computational Technology for All
Computational Technology for All | Sciencx (2025-01-16T00:57:14+00:00) Bridging Computational Notions of Depth: How We Studied the Relationship. Retrieved from https://www.scien.cx/2025/01/16/bridging-computational-notions-of-depth-how-we-studied-the-relationship/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.