Title
An optimal semimeasure and its convergence
Type
Talk
This talk is in ALGI 22 at University of Tokyo on Aug 23, 2011.
Download
slide
The difference between optimality and universality
News
July 16, 2011, Accepted.
June 16, 2011, Resubmitted to a Journal
Mar 29, 2011, Submitted to a Journal
Title
The diifference between optimality and universality
(Former)Degree of non-randomness and uniform Solovay reducibility
Type
Fullpaper
Journal
Logic Journal of the IGPL (2012) 20 (1): 222-234.
abstract page
Abstract
We introduce a degree of non-randomness using a test concept.
The degree implies a notion of an optimal Martin-L\”of test, which is different from a universal test.
In the latter half we generalize Solovay reducibility.
Solovay reducibility is a measure of relative randomness between two reals.
We introduce uniform solovay reducibility, which is a measure of relative randomness between two sequences of reals.
Finally we prove that a sequence is uniform Solovay complete iff it is the sequence of measures of an optimal Martin-L\”of test.