Chaitin Ωnumbers and halting problems - Mathematics > LogicReportar como inadecuado

Chaitin Ωnumbers and halting problems - Mathematics > Logic - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.

Autor: Kohtaro Tadaki


Documentos relacionados