My master thesis (Mar 1995)
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.
My master thesis (Dvi file, in Japanese)
- Kolmogorov complexity
- Martin-L\"of randomness
- Recursion theory
is home page of Kobayasi labo (in Japanese).
is home page of Kobayasi labo (in English).
Home page of Dept. of Information Science (in English).