Posts

Posted on

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.