Share and Export
Share and Export
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
Available under License Creative Commons Attribution Non-commercial Share Alike.
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: | 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 |
| Related URLs: | |
| 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 |
Downloads
Downloads per month over past year
Origin of downloads
Altmetric Badge
Repository Staff Only (login required)
- Item control page
