Truth and Light: Physical Algorithmic Randomness

Show simple item record

dc.contributor.author Stay, M.A en
dc.date.accessioned 2009-04-16T23:15:04Z en
dc.date.available 2009-04-16T23:15:04Z en
dc.date.issued 2005-08 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-271 (2005) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri http://hdl.handle.net/2292/3778 en
dc.description.abstract This thesis examines some problems related to Chaitin’s number. In the first section, we describe several new minimalist prefix-free machines suitable for the study of concrete algorithmic information theory; the halting probabilities of these machines are all numbers. In the second part, we show that when such a sequence is the result given by a measurement of a system, the system itself can be shown to satisfy an uncertainty principle equivalent to Heisenberg’s uncertainty principle. This uncertainty principle also implies Chaitin’s strongest form of incompleteness. In the last part, we show that can be written as an infinite product over halting programs; that there exists a “natural,” or base-free formulation that does not (directly) depend on the alphabet of the universal prefix-free machine; that Tadaki’s generalized halting probability is well-defined even for arbitrary univeral Turing machines and the plain complexity; and finally, that the natural generalized halting probability can be written as an infinite product over primes and has the form of a zeta function whose zeros encode halting information. We conclude with some speculation about physical systems in which partial randomness could arise, and identify many open problems. en
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.relation.isreferencedby UoA1689554 en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. 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 Truth and Light: Physical Algorithmic Randomness 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

Share

Search ResearchSpace


Browse

Statistics