abstract bibtex

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\>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}}

Downloads: 0