Randomness and Computability: Open Questions

DOI10.2178/bsl/1154698740zbMath1169.03033OpenAlexW2110810047MaRDI QIDQ3412462

André Nies, Joseph S. Miller

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/93d1ae4c14a0ee1bb672da73bc19cd56dac15121

Mathematics Subject Classification ID

Descriptive set theory (03E15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)

Related Items

Randomness, Computation and Mathematics, Comparing notions of randomness, Cupping with random sets, Asymptotic density, immunity and randomness, Randomness and universal machines, Random non-cupping revisited, Differences of halting probabilities, Strong jump-traceability. II: \(K\)-triviality, THE COMPUTATIONAL CONTENT OF INTRINSIC DENSITY, STRONG JUMP-TRACEABILITY, Optimal redundancy in computations from random oracles, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, USING ALMOST-EVERYWHERE THEOREMS FROM ANALYSIS TO STUDY RANDOMNESS, Characterizing strong randomness via Martin-Löf randomness, RANDOMNESS NOTIONS AND REVERSE MATHEMATICS, Lowness, Randomness, and Computable Analysis, Upper bounds on ideals in the computably enumerable Turing degrees, Demuth randomness and computational complexity, Some Questions in Computable Mathematics, COMPLEXITY, INFORMATION, ENERGY, Characterizing the strongly jump-traceable sets via randomness, Effective packing dimension of $\Pi ^0_1$-classes, Jump inversions inside effectively closed sets and applications to randomness, A random set which only computes strongly jump-traceable c.e. sets, Strong jump-traceability. I: The computably enumerable case, \(\Pi_1^0 \) classes, LR degrees and Turing degrees, Lowness for Demuth Randomness, Turing degrees of reals of positive effective packing dimension, Extracting Kolmogorov complexity with applications to dimension zero-one laws, Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences, Kolmogorov complexity of initial segments of sequences and arithmetical definability, Hyperimmune-free degrees and Schnorr triviality, Difference randomness, Benign cost functions and lowness properties, 𝐾-trivial degrees and the jump-traceability hierarchy, A universal pair of 1/2-betting strategies, Low upper bounds of ideals, Dimension extractors and optimal decompression, Tracing and domination in the Turing degrees, $K$-triviality in computable metric spaces, Inherent enumerability of strong jump-traceability, Non-cupping and randomness, Denjoy, Demuth and density

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On relative randomness
• Constructive dimension equals Kolmogorov complexity
• Mathematical metaphysics of randomness
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Randomness and reducibility
• Lowness properties and randomness
• Kolmogorov-Loveland randomness and stochasticity
• An almost deep degree
• Computational randomness and lowness
• Algorithmic Randomness and Complexity
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Lowness and nullsets
• Every sequence is reducible to a random one
• The axiomatization of randomness
• Every 2-random real is Kolmogorov random
• Randomness, relativization and Turing degrees