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

{"_id":"je5iCoXhBfmrSEXHv","bibbaseid":"calude-stay-mostprogramsstopquicklyorneverhalt-2006","authorIDs":[],"author_short":["Calude, C. S","Stay, M. A"],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Calude"],"firstnames":["Cristian","S"],"suffixes":[]},{"propositions":[],"lastnames":["Stay"],"firstnames":["Michael","A"],"suffixes":[]}],"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","bibtex":"@Article{Calude2006,\nauthor = {Calude, Cristian S and Stay, Michael A}, \ntitle = {Most Programs Stop Quickly or Never Halt}, \njournal = {arXiv}, \nvolume = {cs.IT}, \nnumber = {}, \npages = {}, \nyear = {2006}, \nabstract = {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.}, \nlocation = {}, \nkeywords = {cs.IT; math.IT}}\n\n\n","author_short":["Calude, C. S","Stay, M. A"],"key":"Calude2006","id":"Calude2006","bibbaseid":"calude-stay-mostprogramsstopquicklyorneverhalt-2006","role":"author","urls":{},"keyword":["cs.IT; math.IT"],"downloads":0},"bibtype":"article","biburl":"https://gist.githubusercontent.com/stuhlmueller/a37ef2ef4f378ebcb73d249fe0f8377a/raw/6f96f6f779501bd9482896af3e4db4de88c35079/references.bib","creationDate":"2020-01-27T02:13:34.635Z","downloads":0,"keywords":["cs.it; math.it"],"search_terms":["programs","stop","quickly","never","halt","calude","stay"],"title":"Most Programs Stop Quickly or Never Halt","year":2006,"dataSources":["hEoKh4ygEAWbAZ5iy"]}