Calibrating Randomness

DOI10.2178/bsl/1154698741zbMath1113.03037OpenAlexW4210959615MaRDI QIDQ3412463

Sebastiaan A. Terwijn, André Nies, Denis R. Hirschfeldt, Rodney G. Downey

Publication date: 6 December 2006

Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

surveyalgorithmic information theorylownessalgorithmic randomness\(K\)-triviality

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Applications of computability and recursion theory (03D80)

Related Items

Bounded Randomness, Expected utility theory from the frequentist perspective, Randomness, Computation and Mathematics, Turing incomparability in Scott sets, Randomness and universal machines, Strong jump-traceability. II: \(K\)-triviality, Randomness? What randomness?, Undecidability of the structure of the Solovay degrees of c.e. reals, Optimal redundancy in computations from random oracles, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Functions that preserve p-randomness, A Pseudo-Random Generator Whose Output is a Normal Sequence, Martin-Löf random generalized Poisson processes, Effectively approximating measurable sets by open sets, Extending and interpreting Post's programme, Some Questions in Computable Mathematics, Characterizing the strongly jump-traceable sets via randomness, Algorithmically Independent Sequences, Effective packing dimension of $\Pi ^0_1$-classes, Binary subtrees with few labeled paths, Schnorr trivial reals: a construction, A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals, Does truth-table of linear norm reduce the one-query tautologies to a random oracle?, Strong jump-traceability. I: The computably enumerable case, Schnorr trivial sets and truth-table reducibility, The upward closure of a perfect thin class, Algorithmically independent sequences, Time-universal data compression, RECOGNIZING STRONG RANDOM REALS, Turing degrees of reals of positive effective packing dimension, Schnorr triviality and genericity, The importance of Π₁⁰ classes in effective randomness, Hyperimmune-free degrees and Schnorr triviality, A minimal pair of 𝐾-degrees, A universal pair of 1/2-betting strategies, Low upper bounds of ideals, Lowness for Kurtz randomness, Promptness does not imply superlow cuppability, The strength of the rainbow Ramsey Theorem, Inherent enumerability of strong jump-traceability, MARTIN-LÖF RANDOMNESS IN SPACES OF CLOSED SETS, Lowness properties and randomness, Kolmogorov-Loveland randomness and stochasticity, Unpredictability of complex (pure) strategies, Resource-bounded martingales and computable Dowd-type generic sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A separation of two randomness concepts
• On relative randomness
• Subsequences of normal sequences
• Characterising the Martin-Löf random sequences using computably enumerable sets of measure one
• Constructive dimension equals Kolmogorov complexity
• A mathematical proof of S. Shelah's theorem on the measure problem and related results
• On the notion of infinite pseudorandom sequences
• Incompleteness theorems for random reals
• Almost everywhere high nonuniform complexity
• Mathematical metaphysics of randomness
• Classical recursion theory. Vol. II
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• The fractal nature of Riem/Diff. I.
• Automata, languages and programming. 30th international colloquium, ICALP 2003, Eindhoven, The Netherland, June 30 -- July 4, 2003. Proceedings
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Randomness and reducibility
• On Kurtz randomness
• The dimensions of individual strings and sequences
• The Kolmogorov complexity of random reals
• Process complexity and effective random tests
• Kolmogorov complexity and Hausdorff dimension
• A model of set-theory in which every set of reals is Lebesgue measurable
• Lowness properties and randomness
• On partial randomness
• Kolmogorov-Loveland randomness and stochasticity
• Automorphisms of the lattice of $\Pi _1^0$ classes; perfect thin classes and anc degrees
• Computational randomness and lowness
• Randomness and Recursive Enumerability
• Randomness, Computability, and Density
• Effective fractal dimensions
• On Schnorr and computable randomness, martingales, and machines
• Algorithmic Randomness and Complexity
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion
• Category and Measure in Complexity Classes
• Counting the number of equivalence classes of Borel and coanalytic equivalence relations
• Every sequence is reducible to a random one
• Probabilities over rich languages, testing and randomness
• A Theory of Program Size Formally Identical to Information Theory
• Complexity dips in random infinite binary sequences
• Dimension in Complexity Classes
• Effectively dense Boolean algebras and their applications
• There are 2^{ℵ₀} many 𝐻-degrees in the random reals
• Lowness for the class of random sets
• The axiomatization of randomness
• Schnorr randomness
• On the construction of effectively random sets
• Every 2-random real is Kolmogorov random
• There is no SW-complete c.e. real
• Degrees of Unsolvability. (AM-55)
• The degrees of bi‐immune sets
• A variant of the Kolmogorov concept of complexity
• The Degrees of Hyperimmune Sets
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A unified approach to the definition of random sequences
• The definition of random sequences
• Class groups of integral group rings
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals
• Randomness, relativization and Turing degrees
• Random reals and possibly infinite computations Part I: Randomness in ∅′
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)