Most programs stop quickly or never halt
From MaRDI portal
Publication:2482913
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 -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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1911266 (Why is no real title available?)
- scientific article; zbMATH DE number 5234254 (Why is no real title available?)
- A Theory of Program Size Formally Identical to Information Theory
- Computational power of infinite quantum parallelism
- From Heisenberg to Gödel via Chaitin
- Fundamentals of Computation Theory
- Is complexity a source of incompleteness?
- Natural halting probabilities, partial randomness, and zeta functions
- The halting problem is decidable on a set of asymptotic probability one
Cited in
(18)- Asymptotic behavior and halting probability of Turing machines
- The halting problem is decidable on a set of asymptotic probability one
- Introduction to the special issue: Computability of the physical
- Computable model discovery and high-level-programming approximations to algorithmic complexity
- Anytime algorithms for non-ending computations
- scientific article; zbMATH DE number 4049059 (Why is no real title available?)
- A statistical anytime algorithm for the halting problem
- Asymptotic proportion of hard instances of the halting problem
- A new perspective on intermediate algorithms via the Riemann-Hilbert correspondence
- Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
- Computer runtimes and the length of proofs. With an algorithmic probabilistic application to waiting times in automatic theorem proving
- What percentage of programs halt?
- A Turing test for free will
- A probabilistic anytime algorithm for the halting problem
- Algorithmic thermodynamics
- Information: The Algorithmic Paradigm
- On the generic undecidability of the halting problem for normalized Turing machines
- Renormalisation and computation. II: Time cut-off and the halting problem
This page was built for publication: Most programs stop quickly or never halt
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482913)
