An incomplete set of shortest descriptions

DOI10.2178/jsl/1327068704zbMath1245.03062MaRDI QIDQ5388731

Jason Teutsch, Frank Stephan

Publication date: 19 April 2012

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.jsl/1327068704

zbMATH Keywords

approximability; truth-table degrees; shortest descriptions; retraceability; domain-random strings

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03D30: Other degrees and reducibilities in computability and recursion theory

03D45: Theory of numerations, effectively presented structures

03D32: Algorithmic randomness and dimension

Related Items

Things that can be made into themselves, Searching for shortest and least programs, Effectivity questions for Kleene's recursion theorem, On Approximate Decidability of Minimal Programs

Cites Work

• Unnamed Item
• Randomness and universal machines
• Immunity and hyperimmunity for sets of minimal indices
• Incompleteness theorems for random reals
• A guided tour of minimal indices and shortest descriptions
• Handbook of computability theory
• Recursion theoretic properties of frequency computation and bounded queries
• On the Turing degrees of minimal index sets
• The recursively enumerable degrees are dense
• Interpolation and embedding in the recursively enumerable degrees
• Algorithmic Randomness and Complexity
• Index Sets and Universal Numberings
• Program size in restricted programming languages
• A Theory of Program Size Formally Identical to Information Theory
• On btt‐Degrees of Sets of Minimal Numbers in Gödel Numberings
• Bounded Immunity and Btt-Reductions
• On the size of machines
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences
• Recursive Enumerability and the Jump Operator