Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6873900 | Information and Computation | 2018 | 29 Pages |
Abstract
This paper explores a novel definition of Schnorr randomness for noncomputable measures. We say x is uniformly Schnorr μ-random if t(μ,x)<â for all lower semicomputable functions t(μ,x) such that μâ¦â«t(μ,x)dμ(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öf randomness for noncomputable measures. Nonetheless, a number of our proofs significantly differ from the Martin-Löf case, requiring new ideas from computable analysis.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jason Rute,