Monthly Archives: August 2011

An optimal semimeasure and its convergence

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

Posted in Talks | Leave a comment

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.

Posted in Publication | Leave a comment