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

Characterizing randomness by integral tests

Title
Characterizing randomness by integral tests

Type
Talk

This talk is in CiE 2011 at Sofia University on June 29, 2011.

Download
slide

Posted in Talks | Leave a comment

Characterizing randomness by integral tests

Title
Characterizing randomness by integral tests

Type
Talk

This talk is in CS Seminar at Kyoto University on June 16, 2011.
The same talk will be given in CiE 2011.

Download
slide

Posted in Talks | Leave a comment

A computable topological space of measures

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.

Posted in Publication | Leave a comment

Truth-table Schnorr randomness and truth-table reducible randomness

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}
}

Posted in Publication | Leave a comment

Generalizing randomness

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

Posted in Publication | Leave a comment

Computability of measures and A-topology

Title
Computability of measures and A-topology

Type
Talk

This talk is in “CC-Seminar” at Kyoto Sangyo University on Mar 4, 2011.

Download
slide
Attached slides are in English.

Posted in Talks | Leave a comment

Degree of non-randomness and uniform Solovay reducibility

Title
Degree of non-randomness and uniform Solovay reducibility

Type
Talk

This talk is in
“WORKSHOP ON PROOF THEORY AND COMPUTABILITY THEORY”
at Iwanumaya in Sendai on Feb 23, 2011.

Download
slide
Attached slides are in English.

Posted in Talks | Leave a comment

Towards prediction via randomness

Title
Towards prediction via randomness

Type
Talk

This talk is in
“Statistics for Stochastic Processes: Inference, Asymptotic Methods, Finance and Data Analysis”
at University of Tokyo in Tokyo on Feb 22, 2011.

Download
slide
Attached slides are in English.

Posted in Talks | Leave a comment