Universality, optimality, and randomness deficiency

DOI10.1016/J.APAL.2015.05.006MaRDI QIDQ2352258zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

layerwise computabilityoptimal Martin-Löf testrandomness deficiencyuniversal Martin-Löf testWeihrauch degrees

Mathematics Subject Classification ID

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

Abstract: A Martin-L"of test $mathcalU$ is universal if it captures all non-Martin-L"of random sequences, and it is optimal if for every ML-test $mathcalV$ there is a $cinomega$ such that $foralln(mathcal{V}_{n+c}subseteqmathcal{U}_n)$. We study the computational differences between universal and optimal ML-tests as well as the effects that these differences have on both the notion of layerwise computability and the Weihrauch degree of LAY, the function that produces a bound for a given Martin-L"of random sequence's randomness deficiency. We prove several robustness and idempotence results concerning the Weihrauch degree of LAY, and we show that layerwise computability is more restrictive than Weihrauch reducibility to LAY. Along similar lines we also study the principle RD, a variant of LAY outputting the precise randomness deficiency of sequences instead of only an upper bound as LAY.

Recommendations

• The difference between optimality and universality
• Some results on effective randomness
• Automata, Languages and Programming
• Schnorr randomness
• Hierarchies of randomness tests

Cites work

• 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
• Closed choice and a uniform low basis theorem
• Computability and randomness
• Computability of the ergodic decomposition
• Computable invariance
• Effective Borel measurability and reducibility of functions
• Effective Choice and Boundedness Principles in Computable Analysis
• How incomputable is finding Nash equilibria?
• How incomputable is the separable Hahn-Banach theorem?
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• Las Vegas computability and algorithmic randomness
• Non-deterministic computation and the Jayne-Rogers theorem
• On the (semi)lattices induced by continuous reducibilities
• On the algebraic structure of Weihrauch degrees
• On uniform relationships between combinatorial problems
• Some results on effective randomness
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• The definition of random sequences
• The difference between optimality and universality
• Weihrauch degrees, omniscience principles and weak computability
• Weihrauch-completeness for layerwise computability

Cited in

(7)

• Universality in random moment problems
• Invariance and Universality of Complexity
• The difference between optimality and universality
• Universal redundancy rates do not exist
• Weihrauch-completeness for layerwise computability
• Computable Measure Theory and Algorithmic Randomness
• Computability of convergence rates in the ergodic theorem for Martin-Löf random points

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

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