Share and Export
Share and Export
Moser, Philippe and Stephan, Frank (2018) Limit-depth and DNR degrees. Information Processing Letters, 135. pp. 36-40. ISSN 0020-0190
Preview
PM_computer science_limit depth.pdf
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: | 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 |
| Related URLs: | |
| URI: | https://mural.maynoothuniversity.ie/id/eprint/13190 |
| 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
Downloads per month over past year
