scientific article
From MaRDI portal
Publication:3611832
zbMath1169.03034MaRDI QIDQ3611832
Publication date: 3 March 2009
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
algorithmic information theoryrandom setsrandom sequenceslownessdescriptive complexity\(K\)-trivialityrandom strings
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
Intermediate intrinsic density and randomness ⋮ Genericity of weakly computable objects ⋮ Higher randomness and forcing with closed sets ⋮ 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? ⋮ Strengthening prompt simplicity ⋮ Randomness, Computation and Mathematics ⋮ The Intersection of Algorithmically Random Closed Sets and Effective Dimension ⋮ Effectivity questions for Kleene's recursion theorem ⋮ Initial segment complexities of randomness notions ⋮ DEGREES OF RANDOMIZED COMPUTABILITY ⋮ Cupping with random sets ⋮ Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces ⋮ CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS ⋮ Covering the Recursive Sets ⋮ Randomness and Differentiability of Convex Functions ⋮ Dimension spectra of lines1 ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ LUZIN’S (N) AND RANDOMNESS REFLECTION ⋮ Differences of halting probabilities ⋮ JSL volume 79 issue 2 Cover and Front matter ⋮ On zeros of Martin-Löf random Brownian motion ⋮ RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY ⋮ STRONG JUMP-TRACEABILITY ⋮ On Low for Speed Oracles ⋮ Randomness and uniform distribution modulo one ⋮ On continued fraction randomness and normality ⋮ $$\textit{K}$$-trivial, $$\textit{K}$$-low and $${{\mathrm{\textit{MLR}}}}$$-low Sequences: A Tutorial ⋮ Depth, Highness and DNR Degrees ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ CHAITIN’S Ω AS A CONTINUOUS FUNCTION ⋮ The Kučera-Gács theorem revisited by Levin ⋮ Π11‐Martin‐Löf randomness and Π11‐Solovay completeness ⋮ Relativized depth ⋮ HIGHER RANDOMNESS AND GENERICITY ⋮ Unnamed Item ⋮ Computing from projections of random points ⋮ Orders on computable rings ⋮ On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets ⋮ Lowness, Randomness, and Computable Analysis ⋮ Polynomial clone reducibility ⋮ Borel-Piecewise Continuous Reducibility for Uniformization Problems ⋮ ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER ⋮ 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 ⋮ Unnamed Item ⋮ Fractal Intersections and Products via Algorithmic Dimension ⋮ ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY ⋮ A bounded jump for the bounded Turing degrees ⋮ The axiomatic power of Kolmogorov complexity ⋮ On effectively closed sets of effective strong measure zero ⋮ How much randomness is needed for statistics? ⋮ Algorithmic information theory and its statistical mechanical interpretation ⋮ A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES ⋮ WEAKLY 2-RANDOMS AND 1-GENERICS IN SCOTT SETS ⋮ Jump inversions inside effectively closed sets and applications to randomness ⋮ On the algebraic structure of Weihrauch degrees ⋮ Strong jump-traceability. I: The computably enumerable case ⋮ Random reals, the rainbow Ramsey theorem, and arithmetic conservation ⋮ Uniform distribution and algorithmic randomness ⋮ Selection by Recursively Enumerable Sets ⋮ Unnamed Item ⋮ DEMUTH’S PATH TO RANDOMNESS ⋮ RANDOMNESS IN THE HIGHER SETTING ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Difference randomness ⋮ Benign cost functions and lowness properties ⋮ 𝐾-trivial degrees and the jump-traceability hierarchy ⋮ Lowness for Kurtz randomness ⋮ AN APPLICATION OF RECURSION THEORY TO ANALYSIS ⋮ Randomness and Effective Dimension of Continued Fractions. ⋮ Kolmogorov complexity and strong approximation of Brownian motion ⋮ Increasing the gap between descriptional complexity and algorithmic probability ⋮ Random Subgroups of Rationals ⋮ Relative Kolmogorov complexity and geometry ⋮ $K$-triviality in computable metric spaces ⋮ The strength of the rainbow Ramsey Theorem ⋮ Mass Problems and Measure-Theoretic Regularity ⋮ 2009 North American Annual Meeting of the Association for Symbolic Logic ⋮ Measure and cupping in the Turing degrees ⋮ A note on the join property ⋮ Randomness for non-computable measures ⋮ A computable analysis of majorizing martingales ⋮ Schnorr randomness and the Lebesgue differentiation theorem ⋮ Diagonally Non-Computable Functions and Bi-Immunity ⋮ Unnamed Item ⋮ SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS ⋮ THE REVERSE MATHEMATICS OF THEOREMS OF JORDAN AND LEBESGUE ⋮ Computable Measure Theory and Algorithmic Randomness ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory ⋮ Integer valued betting strategies and Turing degrees ⋮ Feasible analysis, randomness, and base invariance ⋮ Schnorr triviality and its equivalent notions ⋮ Trivial measures are not so trivial ⋮ Cryptography and algorithmic randomness ⋮ Closure of resource-bounded randomness notions under polynomial time permutations ⋮ The computational complexity of module socles ⋮ When does randomness come from randomness? ⋮ The computability, definability, and proof theory of Artinian rings ⋮ Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts ⋮ On the uniform computational content of the Baire category theorem ⋮ Degrees that are not degrees of categoricity ⋮ Mutual dimension and random sequences ⋮ Comparing notions of randomness ⋮ \({\Pi}_1^1\)-Martin-Löf random reals as measures of natural open sets ⋮ Strong jump-traceability. II: \(K\)-triviality ⋮ Lowness and logical depth ⋮ Optimal redundancy in computations from random oracles ⋮ Propagation of partial randomness ⋮ Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension ⋮ Universal computably enumerable sets and initial segment prefix-free complexity ⋮ Simplicity via provability for universal prefix-free Turing machines ⋮ Schnorr randomness for noncomputable measures ⋮ Infinite dimensional proper subspaces of computable vector spaces ⋮ Strict process machine complexity ⋮ Compressibility and Kolmogorov complexity ⋮ The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma ⋮ Characterizing strong randomness via Martin-Löf randomness ⋮ Low upper bounds in the LR degrees ⋮ Effective martingales with restricted wagers ⋮ A generalized characterization of algorithmic probability ⋮ Martin-Löf random generalized Poisson processes ⋮ Effectively approximating measurable sets by open sets ⋮ Closed choice and a uniform low basis theorem ⋮ \(A\)-computable graphs ⋮ Time-bounded Kolmogorov complexity and Solovay functions ⋮ Effective randomness of unions and intersections ⋮ Characterization of Kurtz randomness by a differentiation theorem ⋮ On the gap between trivial and nontrivial initial segment prefix-free complexity ⋮ Oscillation in the initial segment complexity of random reals ⋮ Elementary differences between the degrees of unsolvability and degrees of compressibility ⋮ Higher Kurtz randomness ⋮ The computable Lipschitz degrees of computably enumerable sets are not dense ⋮ Bounded-low sets and the high/low hierarchy ⋮ On the computability of Solomonoff induction and AIXI ⋮ A \(K\)-trivial set which is not jump traceable at certain orders ⋮ A measure-theoretic proof of Turing incomparability ⋮ Upper bounds on ideals in the computably enumerable Turing degrees ⋮ Absolutely no free lunches! ⋮ Limit-depth and DNR degrees ⋮ Descriptive indexicals and epistemic modality ⋮ On fairly low and superlow sets ⋮ Measure, randomness and sublocales ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ Granularity of wagers in games and the possibility of saving ⋮ Bounding the dimension of points on a line ⋮ 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 ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Subcomputable Hausdorff function dimension ⋮ Revisiting Chaitin's incompleteness theorem ⋮ Covering the recursive sets ⋮ Randomness for computable measures and initial segment complexity ⋮ Bi-immunity over different size alphabets ⋮ Two more characterizations of \(K\)-triviality ⋮ Random numbers as probabilities of machine behavior ⋮ Things that can be made into themselves ⋮ Kobayashi compressibility ⋮ The frequent paucity of trivial strings ⋮ Algorithmic randomness and Fourier analysis ⋮ Algorithmically independent sequences ⋮ Universal recursively enumerable sets of strings ⋮ Computable analogs of cardinal characteristics: prediction and rearrangement ⋮ A Chaitin \(\Omega\) number based on compressible strings ⋮ On low for speed oracles ⋮ Algorithmic randomness, reverse mathematics, and the dominated convergence theorem ⋮ Process and truth-table characterisations of randomness ⋮ Representation of left-computable \(\varepsilon \)-random reals ⋮ Kolmogorov complexity of initial segments of sequences and arithmetical definability ⋮ Finite state complexity ⋮ Finite-state independence ⋮ Coherence of reducibilities with randomness notions ⋮ Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness ⋮ Algorithmically random series and Brownian motion ⋮ Prefix-free quantum Kolmogorov complexity ⋮ Searching for shortest and least programs ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega ⋮ Monotonous betting strategies in warped casinos ⋮ Polylog depth, highness and lowness for E ⋮ Randomness and initial segment complexity for measures ⋮ Tracing and domination in the Turing degrees ⋮ Randomness and lowness notions via open covers ⋮ Reductions between types of numberings ⋮ Martin-Löf randomness implies multiple recurrence in effectively closed sets ⋮ Unified characterizations of lowness properties via Kolmogorov complexity ⋮ Thinking with notations: epistemic actions and epistemic activities in mathematical practice ⋮ Cone avoidance and randomness preservation ⋮ Unpredictability of complex (pure) strategies ⋮ Random reals as measures of natural open sets ⋮ Resource-bounded martingales and computable Dowd-type generic sets ⋮ Probabilistic computability and choice ⋮ A reducibility related to being hyperimmune-free ⋮ Universality, optimality, and randomness deficiency ⋮ Finite state incompressible infinite sequences ⋮ Limitwise monotonic spectra and their generalizations ⋮ Randomness extraction in computability theory ⋮ Probabilistic Algorithmic Randomness ⋮ Shift-complex sequences ⋮ DEEP CLASSES ⋮ USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS ⋮ Pushdown and Lempel-Ziv depth ⋮ Continuous randomness via transformations of 2-random sequences ⋮ Agreement reducibility ⋮ Bernoulli randomness and Bernoulli normality ⋮ Two theorems on minimal generalized computable numberings ⋮ Extending the reach of the point-to-set principle ⋮ Effectively infinite classes of numberings of computable families of reals ⋮ MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY ⋮ Martingales in the Study of Randomness ⋮ The complexity of decomposability of computable rings ⋮ Ergodic theorems and converses for PSPACE functions ⋮ SOME CONSEQUENCES OF AND ⋮ A classification of low c.e. sets and the Ershov hierarchy ⋮ Effectively infinite classes of numberings and computable families of reals ⋮ Families of permutations and ideals of Turing degrees ⋮ Two notes on subshifts ⋮ Solovay reducibility and continuity ⋮ MUCHNIK DEGREES AND CARDINAL CHARACTERISTICS ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees ⋮ The importance of Π10 classes in effective randomness ⋮ GENERICITY AND RANDOMNESS WITH ITTMS ⋮ BEING LOW ALONG A SEQUENCE AND ELSEWHERE ⋮ Martin-Löf random quantum states ⋮ MARTIN-LÖF RANDOMNESS IN SPACES OF CLOSED SETS ⋮ Unnamed Item ⋮ Quantum algorithmic randomness ⋮ SEARCHING FOR AN ANALOGUE OF ATR0 IN THE WEIHRAUCH LATTICE ⋮ Degrees of sets having no subsets of higher m- and t t-degree ⋮ Continuous higher randomness
