An incomplete set of shortest descriptions
From MaRDI portal
Publication:5388731
DOI10.2178/jsl/1327068704zbMath1245.03062MaRDI QIDQ5388731
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
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