MURAL - Maynooth University Research Archive Library



    Depth, Highness and DNR degrees


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

    [img]
    Preview
    Download (187kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


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