Most Programs Stop Quickly or Never Halt
<|reference_start|>Most Programs Stop Quickly or Never Halt: 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.<|reference_end|>
@article{calude2006most,
    title={Most Programs Stop Quickly or Never Halt},
    author={Cristian S. Calude and Michael A. Stay},
    journal={arXiv preprint arXiv:cs/0610153},
    year={2006},
    number={CDMTCS-284},
    archivePrefix={arXiv},
    eprint={cs/0610153},
    primaryClass={cs.IT math.IT}
}