Algorithmic Randomness and Complexity
From MaRDI portal
Publication:3161424
DOI10.1007/978-0-387-68441-3zbMath1221.68005OpenAlexW1574049752MaRDI QIDQ3161424
Denis R. Hirschfeldt, Rodney G. Downey
Publication date: 14 October 2010
Published in: Theory and Applications of Computability (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-0-387-68441-3
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
Non-deterministic effects in a realizability model, The Kolmogorov complexity of random reals, The smallest probability interval a sequence is random for: a study for six types of randomness, Effectivity questions for Kleene's recursion theorem, Splitting into degrees with low computational strength, Initial segment complexities of randomness notions, Approximating approximate reasoning: fuzzy sets and the Ershov hierarchy, Is complexity a source of incompleteness?, Bohmian mechanics is not deterministic, Automatic Kolmogorov complexity, normality, and finite-state dimension revisited, Coloring trees in reverse mathematics, Differences of halting probabilities, The reverse mathematics of non-decreasing subsequences, Where join preservation fails in the bounded Turing degrees of c.e. sets, Randomness? What randomness?, Enumerations including laconic enumerators, Randomness and uniform distribution modulo one, On continued fraction randomness and normality, Compressibility and Kolmogorov complexity, Randomness of formal languages via automatic martingales, 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, Polynomial clone reducibility, A note on density estimation for binary sequences, Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions, Independence, relative randomness, and PA degrees, Lowness for difference tests, Base invariance of feasible dimension, Granularity of wagers in games and the possibility of saving, Bounding the dimension of points on a line, Proofs of conservation inequalities for Levin's notion of mutual information of 1974, The axiomatic power of Kolmogorov complexity, Generics for computable Mathias forcing, On effectively closed sets of effective strong measure zero, How much randomness is needed for statistics?, \textit{CEA} operators and the ershov hierarchy, Subcomputable Hausdorff function dimension, Revisiting Chaitin's incompleteness theorem, 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, Strong jump-traceability. I: The computably enumerable case, A savings paradox for integer-valued gambling strategies, A new quantum random number generator certified by value indefiniteness, Things that can be made into themselves, The frequent paucity of trivial strings, Algorithmic randomness and Fourier analysis, On low for speed oracles, Dimension spectra of lines, On the computational power of random strings, The ibT degrees of computably enumerable sets are not dense, Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness, Computable metrics above the standard real metric, Prefix-free quantum Kolmogorov complexity, Searching for shortest and least programs, 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, Monotonous betting strategies in warped casinos, Polylog depth, highness and lowness for E, Uniform van Lambalgen's theorem fails for computable randomness, Highness properties close to PA completeness, Randomness and initial segment complexity for measures, Fixed point theorems for precomplete numberings, Classical, quantum and biological randomness as relative unpredictability, Preservation of normality by transducers, Algorithmic networks: central time to trigger expected emergent open-endedness, Randomness is inherently imprecise, Reductions between types of numberings, Martin-Löf randomness implies multiple recurrence in effectively closed sets, Algorithmic information dynamics of cellular automata, Multiple genericity: a new transfinite hierarchy of genericity notions, Unified characterizations of lowness properties via Kolmogorov complexity, What can be efficiently reduced to the Kolmogorov-random strings?, On partial randomness, Thinking with notations: epistemic actions and epistemic activities in mathematical practice, Cone avoidance and randomness preservation, Unpredictability of complex (pure) strategies, Strong Medvedev reducibilities and the KL-randomness problem, Random reals as measures of natural open sets, Resource-bounded martingales and computable Dowd-type generic sets, Probabilistic computability and choice, On the (dis)similarities between stationary imprecise and non-stationary precise uncertainty models in algorithmic randomness, 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, 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, Randomness extraction in computability theory, Intermediate intrinsic density and randomness, A Quest for Algorithmically Random Infinite Structures, II, Speedable Left-c.e. Numbers, UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS, The Intersection of Algorithmically Random Closed Sets and Effective Dimension, Probabilistic Algorithmic Randomness, Shift-complex sequences, Turing incomparability in Scott sets, DEGREES OF RANDOMIZED COMPUTABILITY, NOTES ON THE DPRM PROPERTY FOR LISTABLE STRUCTURES, Dimension spectra of lines1, Unnamed Item, INFINITE STRINGS AND THEIR LARGE SCALE PROPERTIES, LUZIN’S (N) AND RANDOMNESS REFLECTION, AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES, RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY, THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY, Capacitability for Co-Analytic Sets, DEEP CLASSES, USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS, A NOTE ON THE LEARNING-THEORETIC CHARACTERIZATIONS OF RANDOMNESS AND CONVERGENCE, THE DETERMINED PROPERTY OF BAIRE IN REVERSE MATH, RANDOMNESS NOTIONS AND REVERSE MATHEMATICS, CHAITIN’S Ω AS A CONTINUOUS FUNCTION, A MINIMAL PAIR IN THE GENERIC DEGREES, The $\Delta ^0_2$ Turing degrees: Automorphisms and Definability, On unstable and unoptimal prediction, Π11‐Martin‐Löf randomness and Π11‐Solovay completeness, Lowness for isomorphism, countable ideals, and computable traceability, Unnamed Item, Computing from projections of random points, FORCING WITH BUSHY TREES, Normal Numbers and Computer Science, Unnamed Item, Fractal Intersections and Products via Algorithmic Dimension, ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY, A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals, An incomplete set of shortest descriptions, Solovay reducibility and continuity, The Information Content of Typical Reals, Incomputability Emergent, and Higher Type Computation, A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES, On the logical strengths of partial solutions to mathematical problems, The power of backtracking and the confinement of length, RELATIVE DEFINABILITY OF n-GENERICS, GENERALIZATIONS OF THE RECURSION THEOREM, INTRINSIC SMALLNESS, On the algebraic structure of Weihrauch degrees, On the computability of a construction of Brownian motion, Canonical immunity and genericity, Trivial Reals, Random reals, the rainbow Ramsey theorem, and arithmetic conservation, Uniform distribution and algorithmic randomness, Medvedev degrees of two-dimensional subshifts of finite type, A Characterization of Constructive Dimension, Effective Randomness for Computable Probability Measures, Bicompletions of Distance Matrices, Translating the Cantor set by a random real, 2006 Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '06, Completeness, Compactness, Effective Dimensions, Multistep Bayesian Strategy in Coin-Tossing Games and Its Application to Asset Trading Games in Continuous Time, Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees, Unnamed Item, Non-cupping, measure and computably enumerable splittings, On universal computably enumerable prefix codes, A WEAKLY 2-GENERIC WHICH BOUNDS A MINIMAL DEGREE, GENERICITY AND RANDOMNESS WITH ITTMS, A characterization of constructive dimension, Unnamed Item, Unnamed Item, Unnamed Item, Optimal bounds for single-source Kolmogorov extractors, BEING LOW ALONG A SEQUENCE AND ELSEWHERE, ON A METRIC GENERALIZATION OF THE tt-DEGREES AND EFFECTIVE DIMENSION THEORY, Randomness and Effective Dimension of Continued Fractions., Random Subgroups of Rationals, On the computability of perfect subsets of sets with positive measure, Martin-Löf random quantum states, Promptness does not imply superlow cuppability, The strength of the rainbow Ramsey Theorem, Mass Problems and Measure-Theoretic Regularity, Spectra of theories and structures, Cone avoiding closed sets, Inherent enumerability of strong jump-traceability, Measures and their random reals, Unnamed Item, A computable analysis of majorizing martingales, Quantum algorithmic randomness, Degrees of sets having no subsets of higher m- and t t-degree, Asymptotic density and the Ershov hierarchy, Effective randomness for continuous measures, Point Degree Spectra of Represented Spaces, SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS, Continuous higher randomness, Computability of Real Numbers, Computable Measure Theory and Algorithmic Randomness, Algorithmic Fractal Dimensions in Geometric Measure Theory, M. Levin’s construction of absolutely normal numbers with very low discrepancy, Lawvere-Tierney topologies for computability theorists, Lowness for genericity, Whitehead's problem and reverse mathematics, Randomness and reducibility, Reducibilities relating to Schnorr randomness, Relating and contrasting plain and prefix Kolmogorov complexity, When does randomness come from randomness?, The computability, definability, and proof theory of Artinian rings, On Kurtz randomness, Refining the taming of the reverse mathematics zoo, On the uniform computational content of the Baire category theorem, Perfect necklaces, Mutual dimension and random sequences, Comparing notions of randomness, \({\Pi}_1^1\)-Martin-Löf random reals as measures of natural open sets, Natural halting probabilities, partial randomness, and zeta functions, Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers, The deluge of spurious correlations in big data, Randomness and universal machines, Random non-cupping revisited, Randomness and the linear degrees of computability, Program extraction for 2-random reals, Strong jump-traceability. II: \(K\)-triviality, Traces, traceability, and lattices of traces under the set theoretic inclusion, Lowness and logical depth, Undecidability of the structure of the Solovay degrees of c.e. reals, Optimal redundancy in computations from random oracles, Propagation of partial randomness, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Dimension 1 sequences are close to randoms, Universal computably enumerable sets and initial segment prefix-free complexity, Non-low\(_2\)-ness and computable Lipschitz reducibility, Functions that preserve p-randomness, Simplicity via provability for universal prefix-free Turing machines, Schnorr randomness for noncomputable measures, Ramsey-type graph coloring and diagonal non-computability, Infinite dimensional proper subspaces of computable vector spaces, Fixed point theorems on partial randomness, Characterizing strong randomness via Martin-Löf randomness, Effective martingales with restricted wagers, 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, How to build a probability-free casino, Effectively approximating measurable sets by open sets, Oscillation in the initial segment complexity of random reals, Notes on sum-tests and independence tests, Extending and interpreting Post's programme, The computable Lipschitz degrees of computably enumerable sets are not dense, A \(K\)-trivial set which is not jump traceable at certain orders, Maximal pairs of c.e. reals in the computably Lipschitz degrees, Limit-depth and DNR degrees, An algorithmic look at financial volatility, Constraints placed on random sequences by their compressibility, Measure, randomness and sublocales, Characterizing the strongly jump-traceable sets via randomness, Binary subtrees with few labeled paths, Convergence of random series and the rate of convergence of the strong law of large numbers in game-theoretic probability, Derandomization in game-theoretic probability, On the number of infinite sequences with trivial initial segment complexity, Natural factors of the Medvedev lattice capturing IPC, Computability theory. Abstracts from the workshop held January 7--13, 2018, Nondeterministic automatic complexity of overlap-free and almost square-free words, Random sequences with respect to a measure defined by two linear fractional transformations, Solovay functions and their applications in algorithmic randomness, Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs, Fractal dimension versus process complexity, Covering the recursive sets, Randomness for computable measures and initial segment complexity, Irrationality exponent, Hausdorff dimension and effectivization, Diagonally non-computable functions and fireworks, Two more characterizations of \(K\)-triviality, Notes on computable analysis, The upward closure of a perfect thin class, Effectively closed sets of measures and randomness, Random numbers as probabilities of machine behavior, Lowness for bounded randomness, Kobayashi compressibility, Strong reductions in effective randomness, How powerful are integer-valued martingales?, Algorithmically independent sequences, A Chaitin \(\Omega\) number based on compressible strings, Kolmogorov-Loveland stochasticity and Kolmogorov complexity, Turing degrees of reals of positive effective packing dimension, Algorithmic randomness, reverse mathematics, and the dominated convergence theorem, Process and truth-table characterisations of randomness, Kolmogorov complexity of initial segments of sequences and arithmetical definability, Finite state complexity, 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, Computing halting probabilities from other halting probabilities, A uniform version of non-\(\mathrm{low}_{2}\)-ness, Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega, Mass problems associated with effectively closed sets, Turing oracle machines, online computing, and three displacements in computability theory, Turing patterns with Turing machines: emergence and low-level structure formation, Finite state incompressible infinite sequences, Pushdown and Lempel-Ziv depth, Continuous randomness via transformations of 2-random sequences, Agreement reducibility, Limit computability and ultrafilters, Extending the reach of the point-to-set principle, MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY, Martingales in the Study of Randomness, Russell's typicality as another randomness notion, Ergodic theorems and converses for PSPACE functions, Finite-state relative dimension, dimensions of AP subsequences and a finite-state van Lambalgen's theorem, A Pseudo-Random Generator Whose Output is a Normal Sequence, A Theory of Bounded Inductive Rationality, SOME CONSEQUENCES OF AND, Effectively infinite classes of numberings and computable families of reals, Extraction rates of random continuous functionals, Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics), COMPUTABLY COMPACT METRIC SPACES, Turing degrees and randomness for continuous measures, Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective, Growth and irreducibility in path-incompressible trees, Bounded Randomness, On Oscillation-Free Chaitin h-Random Sequences, Phase Transition between Unidirectionality and Bidirectionality, Symmetry of Information: A Closer Look, A real of strictly positive effective packing dimension that does not compute a real of effective packing dimension one, A Survey of Mučnik and Medvedev Degrees, 2011 North American Annual Meeting of the Association for Symbolic Logic, What Percentage of Programs Halt?, Randomness and differentiability, Randomness, Computation and Mathematics, A Correspondence Principle for Exact Constructive Dimension, Asymptotic density, computable traceability, and 1-randomness, The Birth and Early Years of Parameterized Complexity, Time-Bounded Kolmogorov Complexity and Solovay Functions, On notions of computability-theoretic reduction between Π21 principles, A Computational Approach to the Borwein-Ditor Theorem, Cupping with random sets, Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces, A statistical mechanical interpretation of algorithmic information theory III: composite systems and fixed points, COMPLEXITY OF COMPLEXITY AND STRINGS WITH MAXIMAL PLAIN AND PREFIX KOLMOGOROV COMPLEXITY, MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY, Covering the Recursive Sets, $$ITRM$$-Recognizability from Random Oracles, Randomness and Differentiability of Convex Functions, COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS, Unpredictability and Computational Irreducibility, Effective genericity and differentiability, EXACT PAIRS FOR THE IDEAL OF THEK-TRIVIAL SEQUENCES IN THE TURING DEGREES, JSL volume 79 issue 2 Cover and Front matter, On zeros of Martin-Löf random Brownian motion, Genericity and UD-random reals, On Low for Speed Oracles, $$\textit{K}$$-trivial, $$\textit{K}$$-low and $${{\mathrm{\textit{MLR}}}}$$-low Sequences: A Tutorial, On the Unpredictability of Individual Quantum Measurement Outcomes, Depth, Highness and DNR Degrees, Fiber entropy and algorithmic complexity of random orbits, The Kučera-Gács theorem revisited by Levin, On initial segment complexity and degrees of randomness, choice classes, Fixed-parameter decidability: Extending parameterized complexity analysis, Relativized depth, Closed left-r.e. sets, Complexity with Rod, 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, On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets, On the Reals Which Cannot Be Random, A Note on the Differences of Computably Enumerable Reals, Lowness, Randomness, and Computable Analysis, Cameo of a Consummate Computabilist, Some Questions in Computable Mathematics, The Complexity of Complexity, STRONG REDUCTIONS BETWEEN COMBINATORIAL PRINCIPLES, THE DEFINABILITY STRENGTH OF COMBINATORIAL PRINCIPLES, COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS, Algorithmically Independent Sequences, Effective packing dimension of $\Pi ^0_1$-classes, On Resource-Bounded Versions of the van Lambalgen Theorem, Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity, Who Asked Us? How the Theory of Computing Answers Questions about Analysis, Algorithmic information theory and its statistical mechanical interpretation, Truth-table Schnorr randomness and truth-table reducible randomness, Closed Left-R.E. Sets, Jump inversions inside effectively closed sets and applications to randomness, Structures of Some Strong Reducibilities, Immunity for Closed Sets, Chaitin Ω Numbers and Halting Problems, RECOGNIZING STRONG RANDOM REALS, On the degree spectrum of a $\Pi ^0_1$ class, Fixed Point Theorems on Partial Randomness, COMPUTABLE ABELIAN GROUPS, DEMUTH’S PATH TO RANDOMNESS, On uniform relationships between combinatorial problems, A minimal pair of 𝐾-degrees, RELATIVIZING CHAITIN'S HALTING PROBABILITY, Hierarchy of Computably Enumerable Degrees II, Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization, Difference randomness, AN APPLICATION OF RECURSION THEORY TO ANALYSIS, Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension, Measure-theoretic applications of higher Demuth’s Theorem, Towards an Axiomatic System for Kolmogorov Complexity, Increasing the gap between descriptional complexity and algorithmic probability, Computable randomness and betting for computable probability spaces, Relative Kolmogorov complexity and geometry, Measure theory aspects of locally countable orderings, Lowness and nullsets, Randomness and Computability: Open Questions, Calibrating Randomness, Degrees of monotone complexity, Measure and cupping in the Turing degrees, Randomness for non-computable measures, Non-cupping and randomness, When van Lambalgen’s Theorem fails, Schnorr randomness and the Lebesgue differentiation theorem, Diagonally Non-Computable Functions and Bi-Immunity, Denjoy, Demuth and density, Closure of resource-bounded randomness notions under polynomial time permutations
