Chaitin Ωnumbers and halting problems
arXiv:0904.1149 · doi:10.1007/978-3-642-03073-4_46
Abstract
Chaitin [G. J. Chaitin, J. Assoc. Comput. Mach., vol.22, pp.329-340, 1975] introduced Ωnumber as a concrete example of random real. The real Ω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 Ωto be random by discovering the property that the first n bits of the base-two expansion of Ω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 Ωand the halting problem by imposing the restriction to finite size on both the problems. It is known that the base-two expansion of Ωand the halting problem are Turing equivalent. We thus consider an elaboration of the Turing equivalence in a certain manner.
17 pages, LaTeX2e, no figures. This is an earlier full version of the paper that will appear in the Proceedings of Computability in Europe 2009, Heidelberg, Germany, July 19 - 24, 2009