Computational depth and reducibility
From MaRDI portal
Publication:1334655
DOI10.1016/0304-3975(94)00014-XzbMath0821.68052MaRDI QIDQ1334655
David W. Juedes, Jack H. Lutz, James I. Lathrop
Publication date: 25 September 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10)
Related Items
Time-Bounded Kolmogorov Complexity and Solovay Functions ⋮ Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report) ⋮ Weakly useful sequences ⋮ Recursive computational depth ⋮ Depth, Highness and DNR Degrees ⋮ Relativized depth ⋮ Time-bounded Kolmogorov complexity and Solovay functions ⋮ Limit-depth and DNR degrees ⋮ Feasible reductions to Kolmogorov-Loveland stochastic sequences ⋮ On the Polynomial Depth of Various Sets of Random Strings ⋮ Sophistication vs logical depth ⋮ Recursively enumerable reals and Chaitin \(\Omega\) numbers ⋮ Weakly useful sequences ⋮ Searching for shortest and least programs ⋮ Depth as randomness deficiency ⋮ Recursive computational depth.
Cites Work
- Algebra of invariant properties of binary sequences
- Incompleteness theorems for random reals
- Descriptive set theory
- Almost everywhere high nonuniform complexity
- Families of recursive predicates of measure zero
- 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
- Learning Simple Concepts under Simple Distributions
- A Theory of Program Size Formally Identical to Information Theory
- Computational Complexity of Probabilistic Turing Machines
- An observation on probability versus randomness with applications to complexity classes
- On Languages Reducible to Algorithmically Random Languages
- 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 II
- On Suborderings of Degrees of Recursive Unsolvability
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
