Computability and Randomness

DOI10.1093/acprof:oso/9780199230761.001.0001zbMath1237.03027OpenAlexW1579696469MaRDI QIDQ5389159

Publication date: 25 April 2012

Full work available at URL: https://semanticscholar.org/paper/8a8970b398dcd7e2cd37ff7357dcfca31a01579c

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

Related Items

An inside/outside Ramsey theorem and recursion theory, A Quest for Algorithmically Random Infinite Structures, II, Bounded Randomness, Demuth’s Path to Randomness, Phase Transition between Unidirectionality and Bidirectionality, Speedable Left-c.e. Numbers, Reducibilities relating to Schnorr randomness, Randomness and differentiability, Mutual dimension and random sequences, Time-Bounded Kolmogorov Complexity and Solovay Functions, A Computational Approach to the Borwein-Ditor Theorem, The Typical Constructible Object, Lightface $$\mathop {\varPi }\nolimits _{3}^{0}$$ Π 3 0 -Completeness of Density Sets Under Effective Wadge Reducibility, A statistical mechanical interpretation of algorithmic information theory III: composite systems and fixed points, Preservation of normality by unambiguous transducers, Lebesgue's density theorem and definable selectors for ideals, INFINITE STRINGS AND THEIR LARGE SCALE PROPERTIES, Traces, traceability, and lattices of traces under the set theoretic inclusion, On the uniform computational content of computability theory, Extraction rates of random continuous functionals, On the cardinality of future worldlines in discrete spacetime structures, Turing degrees and randomness for continuous measures, Minimal Weak Truth Table Degrees and Computably Enumerable Turing Degrees, Closed left-r.e. sets, Extending and interpreting Post's programme, Weakly Represented Families in Reverse Mathematics, Parallel and Serial Jumps of Weak Weak König’s Lemma, Strength and Weakness in Computable Structure Theory, Asymptotic Density and the Theory of Computability: A Partial Survey, A Note on the Differences of Computably Enumerable Reals, On Work of Barmpalias and Lewis-Pye: A Derivation on the D.C.E. Reals, Demuth randomness and computational complexity, Constraints placed on random sequences by their compressibility, Computably enumerable sets below random sets, A frequentist interpretation of probability for model-based inductive inference, Characterizing the strongly jump-traceable sets via randomness, Universal Recursively Enumerable Sets of Strings, Bounding the dimension of points on a line, Effective packing dimension of $\Pi ^0_1$-classes, On Resource-Bounded Versions of the van Lambalgen Theorem, Who Asked Us? How the Theory of Computing Answers Questions about Analysis, The Information Content of Typical Reals, Randomness and Solovay degrees, A DNC function that computes no effectively bi-immune set, Truth-table Schnorr randomness and truth-table reducible randomness, Pointwise complexity of the derivative of a computable function, Closed Left-R.E. Sets, Gibbs distribution from sequentially predictive form of the second law, Lowness of higher randomness notions, The upward closure of a perfect thin class, Lowness for bounded randomness, Medvedev degrees of two-dimensional subshifts of finite type, Strong reductions in effective randomness, Numberings and Randomness, Chaitin Ω Numbers and Halting Problems, Lowness for effective Hausdorff dimension, Completeness, Compactness, Effective Dimensions, Turing degrees of reals of positive effective packing dimension, Multistep Bayesian Strategy in Coin-Tossing Games and Its Application to Asset Trading Games in Continuous Time, The random members of a ${\Pi }_{1}^{0}$ class, Non-cupping, measure and computably enumerable splittings, On universal computably enumerable prefix codes, Naturalness in Mathematics, Putnam's diagonal argument and the impossibility of a universal learning machine, Optimal bounds for single-source Kolmogorov extractors, Highness properties close to PA completeness, Sub-computabilities, Measure-theoretic applications of higher Demuth’s Theorem, Three Theorems on n-REA Degrees: Proof-Readers and Verifiers, Towards an Axiomatic System for Kolmogorov Complexity, A STRONG LAW OF COMPUTATIONALLY WEAK SUBSETS, Computable randomness and betting for computable probability spaces, On the Computability of Solomonoff Induction and Knowledge-Seeking, Cone avoiding closed sets, Inherent enumerability of strong jump-traceability, Measures and their random reals, Lowness properties and randomness, Multiple genericity: a new transfinite hierarchy of genericity notions, Effective randomness for continuous measures, Strong Medvedev reducibilities and the KL-randomness problem, On trees without hyperimmune branches, Symbolic dynamics: entropy = dimension = complexity, Denjoy, Demuth and density, A Church-Turing thesis for randomness?, KL-randomness and effective dimension under strong reducibility