کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4661697 | 1633449 | 2015 | 21 صفحه PDF | دانلود رایگان |
A Martin-Löf test UU is universal if it captures all non-Martin-Löf random sequences, and it is optimal if for every ML-test VV there is a c∈ωc∈ω such that ∀n(Vn+c⊆Un)∀n(Vn+c⊆Un). 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 LAYLAY, the function that produces a bound for a given Martin-Löf random sequence's randomness deficiency. We prove several robustness and idempotence results concerning the Weihrauch degree of LAYLAY, and we show that layerwise computability is more restrictive than Weihrauch reducibility to LAYLAY. Along similar lines we also study the principle RDRD, a variant of LAYLAY outputting the precise randomness deficiency of sequences instead of only an upper bound as LAYLAY.
Journal: Annals of Pure and Applied Logic - Volume 166, Issue 10, October 2015, Pages 1049–1069