Exact Approximations of Omega Numbers

Show simple item record

dc.contributor.author Calude, C.S en
dc.contributor.author Dinneen, Michael en
dc.date.accessioned 2009-04-16T23:18:41Z en
dc.date.available 2009-04-16T23:18:41Z en
dc.date.issued 2006-12 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-293 (2006) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri http://hdl.handle.net/2292/3800 en
dc.description.abstract A Chaitin Omega number is the halting probability of a universal prefix-free Turing machine. Every Omega number is simultaneously computably enumerable (the limit of a computable, increasing, converging sequence of rationals), and algorithmically random (its binary expansion is an algorithmic random sequence), hence uncomputable. The value of an Omega number is highly machine-dependent. In general, no more than finitely many scattered bits of the binary expansion of an Omega number can be exactly computed; but, in some cases, it is possible to prove that no bit can be computed. In this paper we will simplify and improve both the method and its correctness proof proposed in an earlier paper, and we will compute the exact approximations of two Omega numbers of the same prefix-free Turing machine, which is universal when used with data in base 16 or base 2: we compute 43 exact bits for the base 16 machine and 40 exact bits for the base 2 machine. en
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial en
dc.title Exact Approximations of Omega Numbers en
dc.type Technical Report en
dc.subject.marsden Fields of Research::280000 Information, Computing and Communication Sciences en
dc.rights.holder The author(s) en
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace