Every sequence is reducible to a random one
From MaRDI portal
Publication:3764139
DOI10.1016/S0019-9958(86)80004-3zbMath0628.03024OpenAlexW2006580730WikidataQ56674608 ScholiaQ56674608MaRDI QIDQ3764139
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80004-3
Related Items
Computational depth and reducibility ⋮ Computational depth and reducibility ⋮ Randomness, Computation and Mathematics ⋮ Initial segment complexities of randomness notions ⋮ On a theorem of gács ⋮ On the construction of effectively random sets ⋮ CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS ⋮ Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers ⋮ COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS ⋮ Gacs-Kucera theorem ⋮ Optimal redundancy in computations from random oracles ⋮ Dimension 1 sequences are close to randoms ⋮ Characterizing strong randomness via Martin-Löf randomness ⋮ The Kučera-Gács theorem revisited by Levin ⋮ On initial segment complexity and degrees of randomness ⋮ Randomness as an invariant for number representations ⋮ Relativized depth ⋮ Computing from projections of random points ⋮ Oscillation in the initial segment complexity of random reals ⋮ Demuth randomness and computational complexity ⋮ Some Questions in Computable Mathematics ⋮ Feasible reductions to Kolmogorov-Loveland stochastic sequences ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ Convergence of random series and the rate of convergence of the strong law of large numbers in game-theoretic probability ⋮ A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Jump inversions inside effectively closed sets and applications to randomness ⋮ Bi-immunity over different size alphabets ⋮ Two more characterizations of \(K\)-triviality ⋮ Effectively closed sets of measures and randomness ⋮ RECOGNIZING STRONG RANDOM REALS ⋮ Lowness for effective Hausdorff dimension ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees ⋮ Lowness for the class of random sets ⋮ Bounded Turing reductions and data processing inequalities for sequences ⋮ RELATIVIZING CHAITIN'S HALTING PROBABILITY ⋮ Dimension extractors and optimal decompression ⋮ Uniform van Lambalgen's theorem fails for computable randomness ⋮ BEING LOW ALONG A SEQUENCE AND ELSEWHERE ⋮ Mathematical metaphysics of randomness ⋮ A topological characterization of random sequences ⋮ Lowness and nullsets ⋮ Randomness and Computability: Open Questions ⋮ Calibrating Randomness ⋮ Measures and their random reals ⋮ Π10 classes with complex elements ⋮ Randomness below complete theories of arithmetic
