Rupert Hoelzl: Universality, optimality, and randomness deficiency

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 5 November 2014, 17:00 hrs

Room: S17#04-04, Department of Mathematics, NUS

Speaker: Rupert Hoelzl

Title: Universality, optimality, and randomness deficiency

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

A Martin-Loef test U is universal if it captures all sequences which
are not Martin-Loef random. A test is optimal if for every Martin Loef
test V there is a natural number c such that for all n, the n+c-th
compoment of the test V is a subset of the n-th component of the test
U. We study the computational differences between universal and
optimal Martin-Loef 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-Loef random sequence’s randomness deficiency. We prove
several robustness results concerning the Weihrauch degree of 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.