Algorithmic information theory

This page is only in Japanese.

Posted in Diary | Leave a comment

$L^1$-computability, layerwise computability and Solovay reducibility

News
17 July 2013, published
27 Mar 2013, accepted
19 Sep 2012, submitted

Title
L1-computability, layerwise computability and Solovay reducibility

Type
Full paper

Journal
Computability, 2:15-29, 2013.

Abstract
We propose a hierarchy of classes of functions that corresponds to the hierarchy of randomness notions. Each class of functions converges at the corresponding random points. We give various characterizations of the classes, that is, characterizations via integral tests, L1-computability and layerwise computability. Furthermore, the relation among these classes is formulated using Solovay reducibility for lower semicomputable functions.

Download
preprint

Correction
Proposition 2.3.
Let $\mu$ be a computable measure on a computable metric space.
Then there exists a computable sequence $\{r_n\}$ such that $\mu(\overline{B}(\alpha_i,r_j)\setminus B(\alpha_i, r_j))$ for all $i$ and $j$.

This statement should be the following.
Proposition 2.3.
Let $\mu$ be a computable measure on a computable metric space.
Then there exists a computable sequence $\{r_n\}$ such that
$\{ r_0,r_1, … \}$ is dense in the interval $(0 , \infty)$ and $\mu(\overline{B}(\alpha_i,r_j)\setminus B(\alpha_i, r_j))$ for all $i$ and $j$.

This problem was pointed out by K. Weihrauch on 19 Jan 2014. I appreciate his notice.

Posted in Publication | Leave a comment

Unpredictability of initial points

News
25 Dec 2013, the slide file was uploaded

Title
Unpredictability of initial points

Type
RIMS Workshop: Dynamical Systems and Computation

Download
miyabe-DSC

Posted in Talks | Leave a comment

Variants of Layerwise Computability

News
9 Dec 2013, the slide file was uploaded.
2 Dec 2013, the talk was given.

Title
Variants of Layerwise Computability

Type

ARGENTINA-JAPAN-NEW ZEALAND WORKSHOP, UNIVERSITY OF AUCKLAND

Download
slide

Posted in Talks | Leave a comment

Uniform Kurtz randomness

News
4 Nov 2013, Published online
16 May 2013, Submitted to a Journal

Title
Uniform Kurtz randomness
(with Takayuki Kihara)

Type
Fullpaper

Journal
Journal of Logic and Computation, 24 (4): 863-882, 2014
doi: 10.1093/logcom/ext054

Abstract
We propose studying uniform Kurtz randomness, which is the uni- form relativization of Kurtz randomness. This notion has more natural properties than the usual relativization. For instance, van Lambalgen’s theorem holds for uniform Kurtz randomness while not for (the usual relativization of) Kurtz randomness. Another advantage is that lowness for uniform Kurtz randomness has many characterizations, such as those via complexity, martingales, Kurtz tt-traceability, and Kurtz dimensional measure.

Download
preprint

Posted in Publication | Leave a comment

An optimal superfarthingale and its convergence over a computable topological space

News
Oct, 2013. Online
Sep 3, 2011. Accepted
June 7, 2011. Submitted

Title
An optimal superfarthingale and its convergence over a computable topological space

Type
Conference paper

Conference
Solomonoff 85th Memorial Conference at Melbourne, Australia.

Lecture Notes in Computer Science
Volume 7070 2013
Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence
Papers from the Ray Solomonoff 85th Memorial Conference, Melbourne, VIC, Australia, November 30 – December 2, 2011
http://link.springer.com/book/10.1007/978-3-642-44958-1

Download
preprint

Abstract
We generalize the convergenece of an optimal semimeasure
to a real probability in algorithmic probability by using game-theoretic
probability theory and the theory of computable topology. Two lemmas
in the proof give as corollary the existence of an optimal test and an
optimal integral test, which are important from the point of view of
algorithmic randomness. We only consider an SCT3 space, where we
can approximate the measure of an open set. Our proof of almost-sure
convergence to the real probability by a superfarthingale indicates why
the convergence in Martin-L¨of sense does not hold.

Posted in Publication | Leave a comment

Almost uniform weak n-randomness

News
27 Sep 2013, the slide file was uploaded.

Title
Almost uniform weak n-randomness

Type
Eighth International Conference on Computability, Complexity and Randomness (CCR 2013)

Download
ccr-cs

Posted in Talks | Leave a comment

Being a Lebesgue point for integral tests

News
18 Sep 2013, the slide file was uploaded.

Title
Being a Lebesgue point for integral tests

Type
Asian Logic Conference 2013

Download
slide

Posted in Talks | Leave a comment

$L^1$-computability and Schnorr randomness

News
26 August 2013, the slide file was uploaded.

Title
$L^1$-computability and Schnorr randomness

Type
In a seminar at Universität der Bundeswehr München

Download
slide

Posted in Talks | Leave a comment

The emergence of probability from randomness and games

News
22 August 2013, the slides were uploaded.

Title
The emergence of probability from randomness and games
(with A. Takemura)

Type
Invited talk at Modeling Market Dynamics and Equilibrium – New Challenges, New Horizons

Download
Slide

Posted in Talks | Leave a comment