Complexity oscillations in random reals

Chen Guang Liu; Kazuyuki Tanaka

doi:10.1093/ietisy/e91-d.10.2517

Complexity oscillations in random reals

Chen Guang Liu
, Kazuyuki Tanaka

Tohoku University
Xi'an University of Technology

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

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.

源语言	英语
页（从-至）	2517-2518
页数	2
期刊	IEICE Transactions on Information and Systems
卷	E91-D
期	10
DOI	https://doi.org/10.1093/ietisy/e91-d.10.2517
出版状态	已出版 - 10月 2008
已对外发布	是

访问文件

10.1093/ietisy/e91-d.10.2517

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{2503790efa69479b8fd8a507afc7a684,

title = "Complexity oscillations in random reals",

abstract = "The C-oscillation due to Martin-L{\"o}f shows that \{a\textbackslash{} Vn[C(α → n) ≥ n - O(1)]\} = θ, which also follows \{α\textbackslash{}in[K(α \textbackslash{} n) ≥ n + K(n) - O(1)]\} = θ. By generalizing them, we show that there does not exist a real α such that Vn (K(α \textbackslash{} 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 = "Institute of Electronics Information Communication Engineers",

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 - https://www.scopus.com/pages/publications/68849117384

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 -