Chaitin's halting probability Ω and halting problems (Theoretical Computer Science and Its Applications)
孝太郎 只木 · Kyoto University Research Information Repository (Kyoto University) · 2009
340, 1975] introduced $\Omega$ number as a concrete example of random real.The real $\Omega$ is defined as the probability that an optimal computer halts, where the optimal computer is a universal decoding algorithm used to define the notion of program-size complexity.Chaitin showed $\Omega$ to be random by discovering the property that the first $n$ bits of the base-two expansion of $\Omega$ solve the halting problem of the optimal computer for all binary inputs of length at most $n$ .In the present paper we investigate this property from various aspects.We consider the relative computational power between the base-two expansion of $\Omega$ and the halting problem by imposing the restriction to finite size on both the problems.It is known that the base-two expansion of $\Omega$ and the halting problem are Turing equivalent.We thus consider an elaboration of the Turing equivalence in a certain manner.