Most short programs halt quickly
Cristian S. Calude, Michael Stay · 2006
Since many real-world problems arising in the fields of compiler optimisation, automatised 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. For each program length on a given machine, there is an uncomputable “critical time ” after which no more programs of that length will halt. A quantum algorithm [7, 1] has been shown to solve the halting problem to any degree of certainty less than one and various experimental studies have proposed heuristics that apply to a majority of programs [4, 15]. Is it possible to have a classical effective way to describe this phenomenon? The aim of this paper is to provide a non-quantum analysis; 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