Algorithmic randomness and complexity.
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Algorithmic randomness and dimension (03D32) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Recommendations
Cited in
(only showing first 100 items - show all)- Turing oracle machines, online computing, and three displacements in computability theory
- Whitehead's problem and reverse mathematics
- The computability, definability, and proof theory of Artinian rings
- Refining the taming of the reverse mathematics zoo
- On the uniform computational content of the Baire category theorem
- The deluge of spurious correlations in big data
- Lowness and logical depth
- Optimal redundancy in computations from random oracles
- Dimension 1 sequences are close to randoms
- Non-low\(_2\)-ness and computable Lipschitz reducibility
- Schnorr randomness for noncomputable measures
- Exact constructive and computable dimensions
- A generalized characterization of algorithmic probability
- On the uniform computational content of computability theory
- On the complexity of automatic complexity
- Limit-depth and DNR degrees
- An algorithmic look at financial volatility
- Computability theory. Abstracts from the workshop held January 7--13, 2018
- Two more characterizations of \(K\)-triviality
- Strong reductions in effective randomness
- A Chaitin number based on compressible strings
- Equivalences between learning of data and probability distributions, and their applications
- Finite-state independence
- Liouville, computable, Borel normal and Martin-Löf random numbers
- Coherence of reducibilities with randomness notions
- Effective Hausdorff dimension in general metric spaces
- Randomness and reducibility
- On Kurtz randomness
- The Kolmogorov complexity of random reals
- Compressibility and Kolmogorov complexity
- Time-bounded Kolmogorov complexity and Solovay functions
- Axiomatizing Kolmogorov complexity
- Dimension is compression
- Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
- Characterization of Kurtz randomness by a differentiation theorem
- On the gap between trivial and nontrivial initial segment prefix-free complexity
- Revisiting Chaitin's incompleteness theorem
- A new quantum random number generator certified by value indefiniteness
- Algorithmic randomness and Fourier analysis
- On low for speed oracles
- Dimension spectra of lines
- Computable metrics above the standard real metric
- Prefix-free quantum Kolmogorov complexity
- Turing computability: structural theory
- Putnam's diagonal argument and the impossibility of a universal learning machine
- A universal pair of 1/2-betting strategies
- Normalized information distance and the oscillation hierarchy
- Highness properties close to PA completeness
- Randomness and initial segment complexity for measures
- Preservation of normality by transducers
- Randomness is inherently imprecise
- Algorithmic information dynamics of cellular automata
- Multiple genericity: a new transfinite hierarchy of genericity notions
- Thinking with notations: epistemic actions and epistemic activities in mathematical practice
- Strong Medvedev reducibilities and the KL-randomness problem
- On the (dis)similarities between stationary imprecise and non-stationary precise uncertainty models in algorithmic randomness
- Some observations on mitotic sets
- Randomising realizability
- A Church-Turing thesis for randomness?
- Simple betting and stochasticity
- KL-randomness and effective dimension under strong reducibility
- Non-deterministic effects in a realizability model
- The smallest probability interval a sequence is random for: a study for six types of randomness
- Approximating approximate reasoning: fuzzy sets and the Ershov hierarchy
- Bohmian mechanics is not deterministic
- Randomness? What randomness?
- Granularity of wagers in games and the possibility of saving
- Proofs of conservation inequalities for Levin's notion of mutual information of 1974
- \textit{CEA} operators and the ershov hierarchy
- Subcomputable Hausdorff function dimension
- Pointwise complexity of the derivative of a computable function
- Gibbs distribution from sequentially predictive form of the second law
- Bi-immunity over different size alphabets
- A savings paradox for integer-valued gambling strategies
- Things that can be made into themselves
- The frequent paucity of trivial strings
- On the computational power of random strings
- Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness
- Searching for shortest and least programs
- Monotonous betting strategies in warped casinos
- Polylog depth, highness and lowness for E
- Uniform van Lambalgen's theorem fails for computable randomness
- Fixed point theorems for precomplete numberings
- Classical, quantum and biological randomness as relative unpredictability
- Algorithmic networks: central time to trigger expected emergent open-endedness
- Reductions between types of numberings
- Martin-Löf randomness implies multiple recurrence in effectively closed sets
- Unified characterizations of lowness properties via Kolmogorov complexity
- Cone avoidance and randomness preservation
- Unpredictability of complex (pure) strategies
- Random reals as measures of natural open sets
- Resource-bounded martingales and computable Dowd-type generic sets
- Probabilistic computability and choice
- Universality, optimality, and randomness deficiency
- Integer valued betting strategies and Turing degrees
- Schnorr triviality and its equivalent notions
- Trivial measures are not so trivial
- Symbolic dynamics: entropy = dimension = complexity
- Cryptography and algorithmic randomness
- Weak truth table degrees of structures
This page was built for publication: Algorithmic randomness and complexity.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3161424)
