Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/177530
| Title: | Depth, highness and DNR degrees | Authors: | Moser P. Stephan F. |
Keywords: | Algorithmic randomness theory Bennett logical depth Computability Kolmogorov complexity Randomness |
Issue Date: | 2017 | Publisher: | Discrete Mathematics and Theoretical Computer Science | Citation: | Moser P., Stephan F. (2017). Depth, highness and DNR degrees. Discrete Mathematics and Theoretical Computer Science 19 (4) : 2. ScholarBank@NUS Repository. | Abstract: | We study Bennett deep sequences in the context of recursion theory; in particular we investigate the notions of O(1)-deepK, O(1)-deepC, order-deepK and order-deepC sequences. Our main results are that Martin-Löf random sets are not order-deepC, that every many-one degree contains a set which is not O(1)-deepC, that O(1)-deepC sets and order-deepK sets have high or DNR Turing degree and that no K-trival set is O(1)-deepK. © 2017 by the author(s). | Source Title: | Discrete Mathematics and Theoretical Computer Science | URI: | https://scholarbank.nus.edu.sg/handle/10635/177530 | ISSN: | 1462-7264 |
| Appears in Collections: | Staff Publications Elements |
Show full item record
Files in This Item:
| File | Description | Size | Format | Access Settings | Version | |
|---|---|---|---|---|---|---|
| depth.pdf | 181.32 kB | Adobe PDF | OPEN | Post-print | View/Download |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.