Moser, Philippe and Stephan, Frank (2018) Limit-depth and DNR degrees. Information Processing Letters, 135. pp. 36-40. ISSN 0020-0190

Preview

Download (245kB) | Preview

Abstract

We introduce the notion of limit-depth, as a notion similar to Bennett depth, but well behaved on Turing degrees, as opposed to truth-table degrees for Bennett depth. We show limit-depth satisfies similar properties to Bennett depth, namely both recursive and sufficiently random sequences are not limit-deep, and limit-depth is preserved over Turing degrees. We show both the halting problem and Chaitin’s omega are limit-deep. We show every limit-deep set has DNR wtt-degree, and some limit-cuppable set does not have a limit-deep wtt degree.

Item Type:	Article
Keywords:	Theory of computation; Logical depth; Kolmogorov complexity;
Academic Unit:	Faculty of Science and Engineering > Computer Science
Item ID:	13190
Identification Number:	https://doi.org/10.1016/j.ipl.2018.02.015
Depositing User:	Philippe Moser
Date Deposited:	28 Aug 2020 11:27
Journal or Publication Title:	Information Processing Letters
Publisher:	Elsevier
Refereed:	Yes
URI:	Publisher
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads