Randomness below complete theories of arithmetic

DOI10.1016/j.ic.2022.104983OpenAlexW4308780696MaRDI QIDQ2112795

Wei Wang, George Barmpalias

Publication date: 12 January 2023

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2206.04996

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
• Randomness and the linear degrees of computability
• \(\Pi_1^0\) classes, Peano arithmetic, randomness, and computable domination
• On the polynomial depth of various sets of random strings
• Highness properties close to PA completeness
• The typical Turing degree
• Denjoy, Demuth and density
• Depth, Highness and DNR Degrees
• Kolmogorov complexity and the Recursion Theorem
• A note on the join property
• Every sequence is reducible to a random one
• The Information Content of Typical Reals
• Limits of the Kučera–Gács Coding Method
• The importance of Π₁⁰ classes in effective randomness
• Relativizations of randomness and genericity notions
• Probability Inequalities for Sums of Bounded Random Variables
• Forbidden information
• A minimal pair of Π₁⁰ classes
• The definition of random sequences
• ∏ 0 1 Classes and Degrees of Theories

This page was built for publication: Randomness below complete theories of arithmetic