Moser, Philippe and Stephan, Frank (2017) Depth, Highness and DNR degrees. Discrete Mathematics and Theoretical Computer Science, 19 (4). p. 2. ISSN 1462-7264

Preview

Download (187kB) | Preview

Abstract

We study Bennett deep sequences in the context of recursion theory; in particular we investigate the notions ofO(1)-deepK,O(1)-deepC, order-deepKand order-deepCsequences. Our main results are that Martin-L ̈of randomsets are not order-deepC, that every many-one degree contains a set which is notO(1)-deepC, thatO(1)-deepCsetsand order-deepKsets have high or DNR Turing degree and that noK-trival set isO(1)-deepK.

Item Type:	Article
Keywords:	Bennett logical depth; Kolmogorov complexity; algorithmic randomness theory; computability and ran-domness;
Academic Unit:	Faculty of Science and Engineering > Computer Science
Item ID:	11674
Identification Number:	https://doi.org/10.23638/DMTCS-19-4-2
Depositing User:	Philippe Moser
Date Deposited:	12 Nov 2019 12:45
Journal or Publication Title:	Discrete Mathematics and Theoretical Computer Science
Publisher:	Episciences.org
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