Computability and randomness

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

Algorithmic randomness and complexity.
Randomness, computation and mathematics
Algorithmic Randomness
Computability, algorithmic randomness and complexity
Interactions of computability and randomness

Cited in

(only showing first 100 items - show all)

Universal computably enumerable sets and initial segment prefix-free complexity
Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension
The Turing universe in the context of enumeration reducibility
Quantum algorithmic randomness
On fairly low and superlow sets
Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
Process and truth-table characterisations of randomness
Randomness and initial segment complexity for measures
Random reals as measures of natural open sets
Strict process machine complexity
Polynomial clone reducibility
On low for speed oracles
Finite state incompressible infinite sequences
Elementary differences between the degrees of unsolvability and degrees of compressibility
Oscillation in the initial segment complexity of random reals
Universal recursively enumerable sets of strings
Time-bounded Kolmogorov complexity and Solovay functions
Algorithmically independent sequences
Thinking with notations: epistemic actions and epistemic activities in mathematical practice
Jump inversions inside effectively closed sets and applications to randomness
Granularity of wagers in games and the possibility of saving
Algorithmic randomness and Fourier analysis
scientific article; zbMATH DE number 7453171 (Why is no real title available?)
Two notes on subshifts
SOME CONSEQUENCES OF AND
Computability. Randomness, reverse mathematics and hypercomputability
A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one
2011 North American Annual Meeting of the Association for Symbolic Logic, University of California at Berkeley, Berkeley, CA, USA, March 24--27, 2011
Martin-Löf random quantum states
Lowness for difference tests
Low upper bounds in the LR degrees
Calculus of cost functions
Randomness for non-computable measures
Closed choice and a uniform low basis theorem
Integer valued betting strategies and Turing degrees
Continuity theorems for a class of computable operators
Some more results on relativized Chaitin's
Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
A level of Martin-Lof randomness.
K-trivial, K-low and MLR-low sequences: a tutorial
Representation of left-computable \(\varepsilon \)-random reals
Effectively approximating measurable sets by open sets
Finite state complexity
Computable analogs of cardinal characteristics: prediction and rearrangement
𝐾-trivial degrees and the jump-traceability hierarchy
Limitwise monotonic spectra and their generalizations
\(\Pi_1^0\) classes, Peano arithmetic, randomness, and computable domination
Comparing notions of randomness
Relativized depth
A survey of Mučnik and Medvedev degrees
Von Neumann entropy and quantum algorithmic randomness
Effectively infinite classes of numberings and computable families of reals
Families of permutations and ideals of Turing degrees
Π11‐Martin‐Löf randomness and Π11‐Solovay completeness
Measure and cupping in the Turing degrees
scientific article; zbMATH DE number 7204368 (Why is no real title available?)
Kolmogorov complexity and strong approximation of Brownian motion
Subcomputable Hausdorff function dimension
Two theorems on minimal generalized computable numberings
Infinite dimensional proper subspaces of computable vector spaces
On low for speed oracles
Computing from projections of random points
The computational complexity of module socles
Increasing the gap between descriptional complexity and algorithmic probability
Deep _1⁰ classes
Resource-bounded martingales and computable Dowd-type generic sets
Mass problems and measure-theoretic regularity
When does randomness come from randomness?
2009 North American Annual Meeting of the Association for Symbolic Logic
The importance of \(\Pi^0_1\) classes in effective randomness
On randomness, determinism and computability
Randomness and differentiability of convex functions
scientific article; zbMATH DE number 1688364 (Why is no real title available?)
Randomness versus superspeedability
K-triviality in computable metric spaces
What percentage of programs halt?
Pebble-depth
Two more characterizations of \(K\)-triviality
A \(K\)-trivial set which is not jump traceable at certain orders
Diagonally non-computable functions and bi-immunity
Continuous randomness via transformations of 2-random sequences
Pushdown and Lempel-Ziv depth
Solomonoff prediction and Occam's razor
Trivial measures are not so trivial
Random world and quantum mechanics
Orders on computable rings
The computability, definability, and proof theory of Artinian rings
A reducibility related to being hyperimmune-free
Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness
Martingales in the Study of Randomness
Randomness and lowness notions via open covers
The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
Characterizing strong randomness via Martin-Löf randomness
On effectively closed sets of effective strong measure zero
A hierarchy of computably enumerable degrees
On the uniform computational content of the Baire category theorem
Compressibility and Kolmogorov complexity
Cryptography and algorithmic randomness
Bi-immunity over different size alphabets

This page was built for publication: Computability and randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3611832)