dc.contributor.author |
Calude, Cristian |
en |
dc.contributor.author |
Stay, M |
en |
dc.date.accessioned |
2012-03-05T02:13:48Z |
en |
dc.date.issued |
2008 |
en |
dc.identifier.citation |
ADV APPL MATH 40(3):295-308 Mar 2008 |
en |
dc.identifier.issn |
0196-8858 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/12871 |
en |
dc.description.abstract |
The aim of this paper is to provide a probabilistic, but non-quantum, analysis of the Halting Problem. Our approach is to have the probability space extend over both space and time and to consider the probability that a random N-bit program has halted by a random time.We postulate an a priori computable probability distribution on all possible runtimes and we prove that given an integer k >0, we can effectively compute a time bound T such that the probability that an N-bit program will eventually halt given that it has not halted by T is smaller than 2−k. We also show that the set of halting programs (which is computably enumerable, but not computable) can be written as a disjoint union of a computable set and a set of effectively vanishing probability. Finally, we show that “long” runtimes are effectively rare. More formally, the set of times at which an N-bit program can stop after the time 2N+constant has effectively zero density. |
en |
dc.publisher |
Elsevier Inc. |
en |
dc.relation.ispartofseries |
Advances in Applied Mathematics |
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.
Details obtained from http://www.sherpa.ac.uk/romeo/issn/0196-8858/ |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.title |
Most programs stop quickly or never halt |
en |
dc.type |
Journal Article |
en |
dc.identifier.doi |
10.1016/j.aam.2007.01.001 |
en |
pubs.begin-page |
295 |
en |
pubs.volume |
40 |
en |
dc.rights.holder |
Copyright: Elsevier Inc. |
en |
pubs.author-url |
http://pdn.sciencedirect.com.ezproxy.auckland.ac.nz/science?_ob=MiamiImageURL&_cid=272528&_user=140507&_pii=S019688580700036X&_check=y&_origin=article&_zone=toolbar&_coverDate=31-Mar-2008&view=c&originContentFamily=serial&wchp=dGLzVlk-zSkWA&md5=ebf4f44f1aaf731597ba7d6fa0de1c0b/1-s2.0-S019688580700036X-main.pdf |
en |
pubs.end-page |
308 |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/RestrictedAccess |
en |
pubs.subtype |
Article |
en |
pubs.elements-id |
93829 |
en |
pubs.org-id |
Science |
en |
pubs.org-id |
School of Computer Science |
en |
pubs.record-created-at-source-date |
2010-09-01 |
en |