Mathematics – Logic
Scientific paper
2009-04-07
Mathematics
Logic
17 pages, LaTeX2e, no figures. This is an earlier full version of the paper that will appear in the Proceedings of Computabili
Scientific paper
Chaitin [G. J. Chaitin, J. Assoc. Comput. Mach., vol.22, pp.329-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.
No associations
LandOfFree
Chaitin Ωnumbers and halting problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Chaitin Ωnumbers and halting problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chaitin Ωnumbers and halting problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-314313