Complexity oscillations in random reals

Chen Guang Liu; Kazuyuki Tanaka

doi:10.1093/ietisy/e91-d.10.2517

Complexity oscillations in random reals

Research output: Contribution to journal › Article › peer-review

Abstract

The C-oscillation due to Martin-Löf shows that {a\ Vn[C(α → n) ≥ n - O(1)]} = θ, which also follows {α\in[K(α \ n) ≥ n + K(n) - O(1)]} = θ. By generalizing them, we show that there does not exist a real α such that Vn (K(α \ n)≥n + λK(n) - O(1)) for any λ > 0.

Original language	English
Pages (from-to)	2517-2518
Number of pages	2
Journal	IEICE Transactions on Information and Systems
Volume	E91-D
Issue number	10
DOIs	https://doi.org/10.1093/ietisy/e91-d.10.2517
State	Published - Oct 2008
Externally published	Yes

Keywords

Algorithmic randomness
C-oscillation
Kolmogorov complexity

Access to Document

10.1093/ietisy/e91-d.10.2517

Cite this

@article{2503790efa69479b8fd8a507afc7a684,

title = "Complexity oscillations in random reals",

abstract = "The C-oscillation due to Martin-L{\"o}f shows that {a\ Vn[C(α → n) ≥ n - O(1)]} = θ, which also follows {α\in[K(α \ n) ≥ n + K(n) - O(1)]} = θ. By generalizing them, we show that there does not exist a real α such that Vn (K(α \ n)≥n + λK(n) - O(1)) for any λ > 0.",

keywords = "Algorithmic randomness, C-oscillation, Kolmogorov complexity",

author = "Liu, {Chen Guang} and Kazuyuki Tanaka",

year = "2008",

month = oct,

doi = "10.1093/ietisy/e91-d.10.2517",

language = "英语",

volume = "E91-D",

pages = "2517--2518",

journal = "IEICE Transactions on Information and Systems",

issn = "0916-8532",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "10",

}

TY - JOUR

T1 - Complexity oscillations in random reals

AU - Liu, Chen Guang

AU - Tanaka, Kazuyuki

PY - 2008/10

Y1 - 2008/10

N2 - The C-oscillation due to Martin-Löf shows that {a\ Vn[C(α → n) ≥ n - O(1)]} = θ, which also follows {α\in[K(α \ n) ≥ n + K(n) - O(1)]} = θ. By generalizing them, we show that there does not exist a real α such that Vn (K(α \ n)≥n + λK(n) - O(1)) for any λ > 0.

AB - The C-oscillation due to Martin-Löf shows that {a\ Vn[C(α → n) ≥ n - O(1)]} = θ, which also follows {α\in[K(α \ n) ≥ n + K(n) - O(1)]} = θ. By generalizing them, we show that there does not exist a real α such that Vn (K(α \ n)≥n + λK(n) - O(1)) for any λ > 0.

KW - Algorithmic randomness

KW - C-oscillation

KW - Kolmogorov complexity

UR - http://www.scopus.com/inward/record.url?scp=68849117384&partnerID=8YFLogxK

U2 - 10.1093/ietisy/e91-d.10.2517

DO - 10.1093/ietisy/e91-d.10.2517

M3 - 文章

AN - SCOPUS:68849117384

SN - 0916-8532

VL - E91-D

SP - 2517

EP - 2518

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

IS - 10

ER -

Complexity oscillations in random reals

Abstract

Keywords

Access to Document

Other files and links

Cite this