An incomplete set of shortest descriptions
From MaRDI portal
Publication:5388731
DOI10.2178/jsl/1327068704zbMath1245.03062OpenAlexW2008534491MaRDI 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
Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Theory of numerations, effectively presented structures (03D45) Algorithmic randomness and dimension (03D32)
Related Items (4)
Effectivity questions for Kleene's recursion theorem ⋮ Things that can be made into themselves ⋮ Searching for shortest and least programs ⋮ 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
This page was built for publication: An incomplete set of shortest descriptions
