Schnorr randomness for noncomputable measures
| Autor: | Jason Rute |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
010102 general mathematics Algorithmic randomness Mathematics - Logic 0102 computer and information sciences Computer Science::Computational Complexity Mathematical proof 01 natural sciences Computable analysis Computer Science Applications Theoretical Computer Science Mathematics::Logic Computational Theory and Mathematics 010201 computation theory & mathematics FOS: Mathematics 03D32 (Primary) 68Q30 (Secondary) 0101 mathematics Logic (math.LO) Randomness Information Systems Mathematics |
| Zdroj: | Information and Computation. 258:50-78 |
| ISSN: | 0890-5401 |
| Popis: | 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-Lof randomness for noncomputable measures. Nonetheless, a number of our proofs significantly differ from the Martin-Lof case, requiring new ideas from computable analysis. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect