Universality, optimality, and randomness deficiency

DOI10.1016/j.apal.2015.05.006zbMath1386.03047arXiv1409.8589OpenAlexW1482237682WikidataQ57948737 ScholiaQ57948737MaRDI QIDQ2352258

Paul Shafer, Rupert Hölzl

Publication date: 30 June 2015

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

randomness deficiencylayerwise computabilityoptimal Martin-Löf testuniversal Martin-Löf testWeihrauch degrees

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32)

Related Items (3)

Computability of convergence rates in the ergodic theorem for Martin-Löf random points ⋮ Unnamed Item ⋮ Computable Measure Theory and Algorithmic Randomness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• Closed choice and a uniform low basis theorem
• How incomputable is the separable Hahn-Banach theorem?
• Computable invariance
• Computability of the ergodic decomposition
• Some results on effective randomness
• On uniform relationships between combinatorial problems
• The difference between optimality and universality
• Las Vegas Computability and Algorithmic Randomness
• On the (semi)lattices induced by continuous reducibilities
• Weihrauch degrees, omniscience principles and weak computability
• Effective Choice and Boundedness Principles in Computable Analysis
• Effective Borel measurability and reducibility of functions
• Algorithmic Randomness and Complexity
• An Application of Martin-Löf Randomness to Effective Probability Theory
• Applications of Effective Probability Theory to Martin-Löf Randomness
• On the algebraic structure of Weihrauch degrees
• Non-deterministic computation and the Jayne-Rogers Theorem
• The definition of random sequences

This page was built for publication: Universality, optimality, and randomness deficiency