Computability and Randomness
From MaRDI portal
Publication:5389159
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 (85)
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
This page was built for publication: Computability and Randomness
