Most Programs Stop Quickly or Never Halt
| dc.creator | Calude, Cristian S. | |
| dc.creator | Stay, Michael A. | |
| dc.date | 2006-10-26 | |
| dc.date | 2007-01-26 | |
| dc.date.accessioned | 2026-07-07T08:16:47Z | |
| dc.date.available | 2026-07-07T08:16:47Z | |
| dc.description | Since many real-world problems arising in the fields of compiler optimisation, automated software engineering, formal proof systems, and so forth are equivalent to the Halting Problem--the most notorious undecidable problem--there is a growing interest, not only academically, in understanding the problem better and in providing alternative solutions. Halting computations can be recognised by simply running them; the main difficulty is to detect non-halting programs. 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 2^{N+constant} has effectively zero density. | |
| dc.description | Shortened abstract and changed format of references to match Adv. Appl. Math guidelines | |
| dc.identifier | https://arxiv.org/abs/cs/0610153 | |
| dc.identifier | http://arxiv.org/abs/cs/0610153 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/133904 | |
| dc.subject | Information Theory | |
| dc.title | Most Programs Stop Quickly or Never Halt | |
| dc.type | text |