Random strings and truth-table degrees of Turing complete c.e. sets

DOI10.2168/LMCS-10(3:15)2014MaRDI QIDQ2921112zbMATH OpenFDO

Authors Mingzhong Cai, Rachel Epstein, Steffen Lempp, Joseph S. Miller, Rodney G. Downey

Publication date 30 September 2014

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.5636

zbMATH Keywords

truth-table degreesminimal pairrandom stringsstrong reducibilities

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

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

Recommendations

• On the complexity of random strings
• scientific article; zbMATH DE number 4131664
• Degrees of randomized computability
• On the polynomial depth of various sets of random strings
• On the Polynomial Depth of Various Sets of Random Strings
• Nonuniform complexity and the randomness of certain complete languages
• Power of randomization in automata on infinite strings
• Power of Randomization in Automata on Infinite Strings

Cited in

(9)

• Universal computably enumerable sets and initial segment prefix-free complexity
• An incomplete set of shortest descriptions
• The Complexity of Complexity
• Some games on Turing machines and power from random strings
• On low for speed oracles
• On the computational power of C-random strings
• Randomness below complete theories of arithmetic
• A MINIMAL SET LOW FOR SPEED
• On the complexity of random strings

This page was built for publication: Random strings and truth-table degrees of Turing complete c.e. sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921112)