Kenshi Miyabe

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.

The content of the paper will be merged into Algorithmic randomness over general spaces.

News
June 13, 2011, Rejected
Sep 21, 2010, Submitted to a Journal

Title
A computable topological space of measures

Type
Fullpaper

Journal
submitted

Download
Japanese summary

Abstract
We show that the space of bounded non-negative Borel measures on
a computable topological space is also a computable topological space
with A-topology. Then we dene computable measures which may not
be probabilistic and may be even innite. We also study randomness for
non-negative Borel measures which may not be probabilistic.

News
Mar 19, 2011. Added citation information
Mar 7, 2011. Published online
May 18, 2010. The paper “Truth-table Schnorr randomness and truth-table reducible randomness” is accepted by Mathematical Logic Quarterly on May 18, 2010.

Title
Truth-table Schnorr randomness and truth-table reducible randomness

Type
Fullpaper

Journal
Mathematical Logic Quarterly 57(3):323-338, 2011
DOI 10.1002/malq.200910128
Journal Page

Download
preprint
Japanese summary

Abstract
Schnorr randomness and computably randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth-table Schnorr randomness (defined by Franklin and Stephan too only by martingales) and truth-table reducible randomness, for which we prove that van Lambalgen’s Theorem holds. We also show that the classes of truth-table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen’s Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth-table Schnorr randomness.

Cited by
@article{franklin2009van,
title={{van Lambalgen’s Theorem and high degrees}},
author={Franklin, J.N.Y. and Stephan, F.},
year={2009},
publisher={Submitted}
}
@misc{bienvenucharacterizing,
title={Characterizing lowness for Demuth randomness},
author={Bienvenu, L. and Downey, R. and Greenberg, N. and Nies, A. and Turetsky, D.},
publisher={Submitted}
}

News
Feb, 2011, Published
Dec 13, 2010, Submitted

Title
Generalizing randomness

Type
Survey

Journal
RIMS Kokyuroku
No. 1729
“Formal Systems and Computability Theory” (2010/09/13-2010/09-17)
pp. 84-94

Download
preprint