Computer Science – Information Theory
Scientific paper
2006-10-26
Computer Science
Information Theory
Shortened abstract and changed format of references to match Adv. Appl. Math guidelines
Scientific paper
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.
Calude Cristian S.
Stay Michael A.
No associations
LandOfFree
Most Programs Stop Quickly or Never Halt does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Most Programs Stop Quickly or Never Halt, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Most Programs Stop Quickly or Never Halt will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-114207