Mingzhong Cai ; Rodney G Downey ; Rachel Epstein ; Steffen Lempp ; Joseph Miller - Random strings and tt-degrees of Turing complete C.E. sets

lmcs:1126 - Logical Methods in Computer Science, September 10, 2014, Volume 10, Issue 3 - https://doi.org/10.2168/LMCS-10(3:15)2014
Random strings and tt-degrees of Turing complete C.E. setsArticle

Authors: Mingzhong Cai ; Rodney G Downey ; Rachel Epstein ; Steffen Lempp ; Joseph Miller

    We investigate the truth-table degrees of (co-)c.e.\ sets, in particular, sets of random strings. It is known that the set of random strings with respect to any universal prefix-free machine is Turing complete, but that truth-table completeness depends on the choice of universal machine. We show that for such sets of random strings, any finite set of their truth-table degrees do not meet to the degree~0, even within the c.e. truth-table degrees, but when taking the meet over all such truth-table degrees, the infinite meet is indeed~0. The latter result proves a conjecture of Allender, Friedman and Gasarch. We also show that there are two Turing complete c.e. sets whose truth-table degrees form a minimal pair.


    Volume: Volume 10, Issue 3
    Published on: September 10, 2014
    Imported on: March 18, 2014
    Keywords: Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • Randomness, Dimension and Computability; Funder: National Science Foundation; Code: 1001847
    • Recursion Theory and Its Applications; Funder: National Science Foundation; Code: 1266214

    4 Documents citing this article

    Consultation statistics

    This page has been seen 1186 times.
    This article's PDF has been downloaded 321 times.