Generalization of complexity oscillations in infinite sequences

被引：0
作者：
Liu, ChenGuang [1 ]
机构：
[1] Xian Univ Technol, Grad Sch Management Sci, Xian 710048, Peoples R China
来源：
ICNC 2008: FOURTH INTERNATIONAL CONFERENCE ON NATURAL COMPUTATION, VOL 1, PROCEEDINGS | 2008年
关键词：
D O I：
10.1109/ICNC.2008.915
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
The C-oscillation due to Martin-Lof shows that {alpha vertical bar for all n[C(alpha vertical bar n) >= n - O(1)]} = empty set, which also follows {alpha vertical bar for all n[K(alpha vertical bar n) >= n + K(n) - O(1)]} = empty set. By generalizing them, we show that there does not exist alpha real a such that for all n (K(alpha vertical bar n) >= n + lambda K(n) - O(1) for any lambda > 0.
引用
收藏
页码：299 / 303
页数：5
相关论文
共 14 条
[1]  
CALUDE CS, 2002, INFORM THEORY RANDOM
[2]  
Chaitin G. J., 1976, Theoretical Computer Science, V2, P45, DOI 10.1016/0304-3975(76)90005-0
[3]  
DOWNEY R, MONOGRAPHS MATH LOGI
[4]   3 APPROACHES TO QUANTITATIVE DEFINITION OF INFORMATION [J].
KOLMOGOROV, AN .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1968, 2 (02) :157-+
[5]  
Levin L. A., 1974, Problems of Information Transmission, V10, P206
[6]   DEFINITION OF RANDOM SEQUENCES [J].
MARTINLOF, P .
INFORMATION AND CONTROL, 1966, 9 (06) :602-+
[7]   COMPLEXITY OSCILLATIONS IN INFINITE BINARY SEQUENCES [J].
MARTINLOF, P .
ZEITSCHRIFT FUR WAHRSCHEINLICHKEITSTHEORIE UND VERWANDTE GEBIETE, 1971, 19 (03) :225-+
[8]  
MILLER JS, DERIVING MUCHN UNPUB
[9]   Kolmogorov entropy in the context of computability theory [J].
Muchnik, AA ;
Positselsky, SY .
THEORETICAL COMPUTER SCIENCE, 2002, 271 (1-2) :15-35
[10]  
Soare R., 1987, RECURSIVELY ENUMERAB
12