

























In 1975 Chaitin introduced his Ωnumber as a concrete example of random real. The real Ωis defined based on the set of all halting inputs for an optimal prefix-free machine U, which is a universal decoding algorithm used to define the notion of program-size complexity. Chaitin showed Ωto be random by discovering the property that the first n bits of the base-two expansion of Ωsolve the halting problem of U for all binary inputs of length at most n. In this paper, we introduce a new representation Θof Chaitin Ωnumber. The real Θis defined based on the set of all compressible strings. We investigate the properties of Θand show that Θis random. In addition, we generalize Θto two directions Θ(T) and \barΘ(T) with a real T>0. We then study their properties. In particular, we show that the computability of the real Θ(T) gives a sufficient condition for a real T in (0,1) to be a fixed point on partial randomness, i.e., to satisfy the condition that the compression rate of T equals to T.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。