On partial randomness
详细信息 查看全文
- 作者：Cristian S. Calude ; Ludwig Staiger and Sebastiaan A. Terwijn
- 关键词：Program-size complexity ; Hausdorff dimension ; Martingales ; (Partial) randomness
- 刊名：Annals of Pure and Applied Logic
- 出版年：2006
- 出版时间：March 2006
- 年：2006
- 卷：138
- 期：1-3
- 页码：20-30
- 全文大小：198 K
文摘
If is a random sequence, then the sequence is clearly not random; however, seems to be “about half random”. L. Staiger [Kolmogorov complexity and Hausdorff dimension, Inform. and Comput. 103 (1993) 159–194 and A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory Comput. Syst. 31 (1998) 215–229] and K. Tadaki [A generalisation of Chaitin’s halting probability Ω and halting self-similar sets, Hokkaido Math. J. 31 (2002) 219–253] have studied the degree of randomness of sequences or reals by measuring their “degree of compression”. This line of study leads to various definitions of partial randomness. In this paper we explore some relations between these definitions. Among other results we obtain a characterisation of 35a2430369badd4b2ea"" title=""Click to view the MathML source"">Σ1-dimension (as defined by Schnorr and Lutz in terms of martingales) in terms of strong Martin-Löf ε-tests (a variant of Martin-Löf tests), and we show that ε-randomness for ε(0,1) is different (and more difficult to study) than the classical 1-randomness.