Most Programs Stop Quickly or Never Halt. Calude, C. S & Stay, M. A arXiv, cs.IT, 2006.
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.
@Article{Calude2006,
author = {Calude, Cristian S and Stay, Michael A},
title = {Most Programs Stop Quickly or Never Halt},
journal = {arXiv},
volume = {cs.IT},
number = {},
pages = {},
year = {2006},
abstract = {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\&gt;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.},
location = {},
keywords = {cs.IT; math.IT}}