Universality, optimality, and randomness deficiency

DOI10.1016/J.APAL.2015.05.006zbMATH Open1386.03047DBLPjournals/apal/HolzlS15arXiv1409.8589OpenAlexW1482237682WikidataQ57948737 ScholiaQ57948737MaRDI QIDQ2352258FDOQ2352258

Authors: Paul Shafer, Rupert Hölzl 

Publication date: 30 June 2015

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

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.

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

Recommendations

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

zbMATH Keywords

randomness deficiencylayerwise computabilityWeihrauch degreesoptimal Martin-Löf testuniversal Martin-Löf test

Mathematics Subject Classification ID

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

Cites Work

• Algorithmic randomness and complexity.
• Computability and randomness
• Title not available (Why is that?)
• The definition of random sequences
• Some results on effective randomness
• An application of Martin-Löf randomness to effective probability theory
• Applications of Effective Probability Theory to Martin-Löf Randomness
• How incomputable is finding Nash equilibria?
• Weihrauch degrees, omniscience principles and weak computability
• Computable invariance
• On the (semi)lattices induced by continuous reducibilities
• Effective Choice and Boundedness Principles in Computable Analysis
• Effective Borel measurability and reducibility of functions
• 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?
• On uniform relationships between combinatorial problems
• Non-deterministic computation and the Jayne-Rogers theorem
• On the algebraic structure of Weihrauch degrees
• Weihrauch-completeness for layerwise computability
• Computability of the ergodic decomposition
• Las Vegas computability and algorithmic randomness
• The difference between optimality and universality

Cited In (7)

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

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)