On initial segment complexity and degrees of randomness
From MaRDI portal
Publication:3506714
DOI10.1090/S0002-9947-08-04395-XzbMath1140.68028MaRDI QIDQ3506714
Publication date: 17 June 2008
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
Energy randomness, Phase Transition between Unidirectionality and Bidirectionality, The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite, Reducibilities relating to Schnorr randomness, Large Turing independent sets, DEGREES OF RANDOMIZED COMPUTABILITY, LUZIN’S (N) AND RANDOMNESS REFLECTION, Propagation of partial randomness, Universal computably enumerable sets and initial segment prefix-free complexity, Characterizing strong randomness via Martin-Löf randomness, CHAITIN’S Ω AS A CONTINUOUS FUNCTION, Two-Way Non-Uniform Finite Automata, Oscillation in the initial segment complexity of random reals, On Resource-Bounded Versions of the van Lambalgen Theorem, A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals, Random reals à la Chaitin with or without prefix-freeness, Algorithmic information theory and its statistical mechanical interpretation, Solovay functions and their applications in algorithmic randomness, Two more characterizations of \(K\)-triviality, Strong jump-traceability. I: The computably enumerable case, Things that can be made into themselves, Chaitin Ω Numbers and Halting Problems, On Martin’s pointed tree theorem, Kolmogorov complexity of initial segments of sequences and arithmetical definability, Coherence of reducibilities with randomness notions, DEMUTH’S PATH TO RANDOMNESS, BEING LOW ALONG A SEQUENCE AND ELSEWHERE, Measure-theoretic applications of higher Demuth’s Theorem, Chaitin's halting probability and the compression of strings using oracles, Randomness and initial segment complexity for measures, Martin-Löf random quantum states, Non-cupping and randomness, Lowness properties and randomness, Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness, Kolmogorov-Loveland randomness and stochasticity, Cone avoidance and randomness preservation, Continuous higher randomness, Cryptography and algorithmic randomness
Cites Work
- Oscillation in the initial segment complexity of random reals
- Incompleteness theorems for random reals
- Randomness and reducibility
- The Kolmogorov complexity of random reals
- Lowness properties and randomness
- Algorithmic Randomness and Complexity
- RELATIVIZING CHAITIN'S HALTING PROBABILITY
- Every 1-generic computes a properly 1-generic
- Every sequence is reducible to a random one
- Von Mises' definition of random sequences reconsidered
- Exact Expressions for Some Randomness Tests
- A Theory of Program Size Formally Identical to Information Theory
- There are 2^{ℵ₀} many 𝐻-degrees in the random reals
- Lowness for the class of random sets
- The axiomatization of randomness
- Every 2-random real is Kolmogorov random
- Degrees of Unsolvability. (AM-55)
- Three approaches to the quantitative definition of information*
- 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
- Randomness, relativization and Turing degrees
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
