Schnorr randomness for noncomputable measures

DOI10.1016/J.IC.2017.10.001MaRDI QIDQ1686119zbMATH OpenOpenAlexFDO

Authors Jason Rute

Publication date 20 December 2017

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

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

zbMATH Keywords

algorithmic randomnessSchnorr randomnessnoncomputable measuresuniform integral tests

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: This paper explores a novel definition of Schnorr randomness for noncomputable measures. We say $x$ is uniformly Schnorr $mu$-random if $t(mu,x)<infty$ for all lower semicomputable functions $t(mu,x)$ such that $mumapstointt(mu,x),dmu(x)$ is computable. We prove a number of theorems demonstrating that this is the correct definition which enjoys many of the same properties as Martin-L"of randomness for noncomputable measures. Nonetheless, a number of our proofs significantly differ from the Martin-L"of case, requiring new ideas from computable analysis.

Recommendations

• Subcomputable Schnorr randomness
• Schnorr randomness
• Schnorr randomness
• Relativizations of randomness and genericity notions
• Reducibilities relating to Schnorr randomness

Cites work

• scientific article; zbMATH DE number 5722526 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 3532844 (Why is no real title available?)
• scientific article; zbMATH DE number 1746049 (Why is no real title available?)
• scientific article; zbMATH DE number 3452925 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• A tutorial on computable analysis
• Algorithmic randomness and complexity.
• Algorithmic randomness and monotone complexity on product space
• Algorithmic tests and randomness with respect to a class of measures
• An application of Martin-Löf randomness to effective probability theory
• An introduction to Kolmogorov complexity and its applications
• An introduction to measure theory
• Applications of Effective Probability Theory to Martin-Löf Randomness
• Brownian motion, bridge excursion, and meander characterized by sampling at independent uniform times
• Computability and randomness
• Computability of probability measures and Martin-Löf randomness over metric spaces
• Computability of the ergodic decomposition
• Conditional probabilities and van Lambalgen's theorem revisited
• Cone avoidance and randomness preservation
• Effectively closed sets of measures and randomness
• Eine Bemerkung zum Begriff der zuf�lligen Folge
• General random sequences and learnable sequences
• Independence, relative randomness, and PA degrees
• Infinite subsets of random sets of integers
• Kolmogorov-Loveland randomness and stochasticity
• Layerwise computability and image randomness
• Lowness for the Class of Schnorr Random Reals
• Martin-Löf randomness and Galton-Watson processes
• Measures and their random reals
• On a definition of random sequences with respect to conditional probability
• On zeros of Martin-Löf random Brownian motion
• Randomness and differentiability
• Randomness and lowness notions via open covers
• Randomness and the ergodic decomposition
• Randomness for non-computable measures
• Schnorr randomness and the Lebesgue differentiation theorem
• Schnorr trivial sets and truth-table reducibility
• Strong reductions in effective randomness
• The axiomatization of randomness
• The definition of random sequences
• The probability distribution as a computational resource for randomness testing
• Truth-table Schnorr randomness and truth-table reducible randomness
• Uniform test of algorithmic randomness over a general space
• Uniform van Lambalgen's theorem fails for computable randomness
• Van Lambalgen's theorem for uniformly relative Schnorr and computable randomness
• Von Neumann's biased coin revisited
• When does randomness come from randomness?
• When van Lambalgen’s Theorem fails
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• \(K\)-trivials are never continuously random
• \(L^1\)-computability, layerwise computability and Solovay reducibility

Cited in

(5)

• Subcomputable Schnorr randomness
• Schnorr randomness and the Lebesgue differentiation theorem
• Schnorr randomness
• Schnorr randomness
• Computable Measure Theory and Algorithmic Randomness

This page was built for publication: Schnorr randomness for noncomputable measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1686119)