Monthly Archives: August 2011
An optimal semimeasure and its convergence
This talk is in ALGI 22 at University of Tokyo on Aug 23, 2011.
July 16, 2011, Accepted.
June 16, 2011, Resubmitted to a Journal
Mar 29, 2011, Submitted to a Journal
The diifference between optimality and universality
(Former)Degree of non-randomness and uniform Solovay reducibility
Logic Journal of the IGPL (2012) 20 (1): 222-234.
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.