Fixed Points on Partial Randomness.
Kohtaro Tadaki · 2009
Algorithmic information theory (AIT, for short) is a theory of program-size and algorithmic ran-domness. One of the primary concepts of AIT is the Kolmogorov complexity K(s) of a finite binary string s, which is defined as the length of the shortest binary program for a universal decoding algo-rithm to output s. In this paper, we report on a quite new type of fixed point in computer science, called a fixed point on partial randomness. In the research of AIT, it is important to consider the notion of the compression rate of a real T, which is defined as the real limn→∞K(Tn)/n, where Tn is the first n bits of the base-two expansion of T. The notion of the partial randomness of a real is a stronger representation of the compression rate. Our fixed point theorems on partial randomness give sufficient conditions for a real T ∈ (0,1) to satisfy that the partial randomness of T equals to T and therefore the compression rate of T equals to T. The fixed point theorems are obtained in the frame-work of the statistical mechanical interpretation of AIT developed by our works [K. Tadaki, Local Proceedings of CiE 2008, pp. 425–434, 2008] and [K. Tadaki, Proceedings of LFCS’09, Springer’s LNCS, vol. 5407, pp. 422–440, 2009]. As an original contribution of this paper, we present a simple and self-contained proof of the fixed point theorem on partial randomness. Key words: algorithmic information theory, algorithmic randomness, Kolmogorov complex-ity, fixed point theorem, partial randomness, compression rate, Chaitin Ω number, statistical mechanics, temperature 1