MURAL - Maynooth University Research Archive Library



    Limit-depth and DNR degrees


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

    [img]
    Preview
    Download (245kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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:
    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)

    View Item Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads