Transactions of the American Mathematical Society · 2013 · 39 citations · 14 references
Natural SciencesComputer ScienceMathematicsProbability TheorySet TheoryTheory Of ComputationComputational Complexity ClassesMeasure-theoretic ProbabilityTuring Degrees
Different approaches have been taken to defining randomness for non-computable probability measures. We will explain the approach of Reimann and Slaman, along with the uniform test approach first introduced by Levin and also used by Gács, Hoyrup and Rojas. We will show that these approaches are fundamentally equivalent. Having clarified what it means to be random for a non-computable probability measure, we turn our attention to Levin’s <italic>neutral measures</italic> , for which all sequences are random. We show that every PA degree computes a neutral measure. We also show that a neutral measure has no least Turing degree representation and explain why the framework of the continuous degrees (a substructure of the enumeration degrees studied by Miller) can be used to determine the computational complexity of neutral measures. This allows us to show that the Turing ideals below neutral measures are exactly the Scott ideals. Since <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X element-of 2 Superscript omega"> <mml:semantics> <mml:mrow> <mml:mi>X</mml:mi> <mml:mo> ∈ </mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mi> ω </mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">X\in 2^\omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is an atom of a neutral measure <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mu"> <mml:semantics> <mml:mi> μ </mml:mi> <mml:annotation encoding="application/x-tex">\mu</mml:annotation> </mml:semantics> </mml:math> </inline-formula> if and only if it is computable from (every representation of) <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mu"> <mml:semantics> <mml:mi> μ </mml:mi> <mml:annotation encoding="application/x-tex">\mu</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , we have a complete understanding of the possible sets of atoms of a neutral measure. One simple consequence is that every neutral measure has a Martin-Löf random atom.
14
The definition of random sequences
Per Martin-Löf · Information and Control · 1966 · 1.2K citations
A generalization of Brouwer’s fixed point theorem
Shizuo Kakutani · Duke Mathematical Journal · 1941 · 1.2K citations