# Chaitin Ωnumbers and halting problems - Mathematics > Logic

Chaitin Ωnumbers and halting problems - Mathematics > Logic - Download this document for free, or read online. Document in PDF available to download.

Abstract: Chaitin G. J. Chaitin, J. Assoc. Comput. Mach., vol.22, pp.329-340, 1975introduced \Omega number as a concrete example of random real. The real \Omegais defined as the probability that an optimal computer halts, where the optimalcomputer is a universal decoding algorithm used to define the notion ofprogram-size complexity. Chaitin showed \Omega to be random by discovering theproperty that the first n bits of the base-two expansion of \Omega solve thehalting problem of the optimal computer for all binary inputs of length at mostn. In the present paper we investigate this property from various aspects. Weconsider the relative computational power between the base-two expansion of\Omega and the halting problem by imposing the restriction to finite size onboth the problems. It is known that the base-two expansion of \Omega and thehalting problem are Turing equivalent. We thus consider an elaboration of theTuring equivalence in a certain manner.

Author: ** Kohtaro Tadaki**

Source: https://arxiv.org/