My master thesis (Mar 1995)

English Abstract

There are several definitions for randomness of infinite binary sequences. One definition(Chaitin randomness) uses Kolmogorov complexity, and another(Martin-L\"of randomness) uses tests. It is a well known result that Chaitin randomness and Martin-L\"of randomness are equivalent. So, infinite binary sequences having high Kolmogorov complexity are characterized by tests.

In this paper, we show one characterization of infinite binary sequences having partial randomness that is similar to Martin-L\"of randomness. We study the relationship between this characterization and the characterization that uses Kolmogorov complexity of infinite binary sequences.

Key words

My master thesis (Dvi file, in Japanese)

Here is home page of Kobayasi labo (in Japanese).

Here is home page of Kobayasi labo (in English).

Home page of Dept. of Information Science (in English).

nagoya@is.titech.ac.jp