| Presentation | 1995/4/21 A Characterization of Infinite Binary Sequences with Low Kolmogorov Complexity Kojiro Kobayashi, Hiroaki Nagoya, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | There are several definitions for randomness of infinite binary sequences. One definition (Chaitin randomness) uses Kolmogorov complexity, and another (Martin-Lof randomness) uses tests. It is a well known result that Chaitin randomness and Martin-Lof 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-Lof randomness. We study the relationship between this characterization and the characterization that uses Kolmogorov complexity of infinite binary sequences. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Kolmogorov complexity / Martin-Lof randomness / recursion theory |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1995/4/21(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Characterization of Infinite Binary Sequences with Low Kolmogorov Complexity |
| Sub Title (in English) | |
| Keyword(1) | Kolmogorov complexity |
| Keyword(2) | Martin-Lof randomness |
| Keyword(3) | recursion theory |
| 1st Author's Name | Kojiro Kobayashi |
| 1st Author's Affiliation | Tokyo Institute of Technology() |
| 2nd Author's Name | Hiroaki Nagoya |
| 2nd Author's Affiliation | Tokyo Institute of Technology |
| Date | 1995/4/21 |
| Paper # | |
| Volume (vol) | vol.95 |
| Number (no) | 13 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |