Computational depth and reducibility
From MaRDI portal
Publication:4630267
DOI10.1007/3-540-56939-1_79zbMath1422.68145OpenAlexW1569304014MaRDI QIDQ4630267
David W. Juedes, Jack H. Lutz, James I. Lathrop
Publication date: 29 March 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://lib.dr.iastate.edu/cs_techreports/72
Baire category, Baire spaces (54E52) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algebra of invariant properties of binary sequences
- Incompleteness theorems for random reals
- Almost everywhere high nonuniform complexity
- Process complexity and effective random tests
- Randomness conservation inequalities; information and independence in mathematical theories
- Every sequence is reducible to a random one
- Algorithms and Randomness
- A Theory of Program Size Formally Identical to Information Theory
- An observation on probability versus randomness with applications to complexity classes
- On Languages Reducible to Algorithmically Random Languages
- Degrees of Unsolvability. (AM-55)
- On the Length of Programs for Computing Finite Binary Sequences
- Logical basis for information theory and probability theory
- Classes of Recursively Enumerable Sets and Degrees of Unsolvability
- On the Length of Programs for Computing Finite Binary Sequences
- Complexity oscillations in infinite binary sequences
- 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
- A formal theory of inductive inference. Part I
