Most programs stop quickly or never halt

DOI10.1016/J.AAM.2007.01.001zbMATH Open1137.68031arXivcs/0610153OpenAlexW2065272524WikidataQ57001609 ScholiaQ57001609MaRDI QIDQ2482913FDOQ2482913

Authors: Cristian S. Calude, Michael Stay 

Publication date: 28 April 2008

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0610153

Recommendations

• What percentage of programs halt?
• The problem of termination of programs
• Termination of well-moded programs
• A program-controlled program interruption system
• Termination of Real-Time Programs: Definitely, Definitely Not, or Maybe
• When programs have to watch paint dry

zbMATH Keywords

halting problemhalting probabilityeffective density

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10)

Cites Work

• Title not available (Why is that?)
• A Theory of Program Size Formally Identical to Information Theory
• Natural halting probabilities, partial randomness, and zeta functions
• Is complexity a source of incompleteness?
• Computational power of infinite quantum parallelism
• Title not available (Why is that?)
• The halting problem is decidable on a set of asymptotic probability one
• From Heisenberg to Gödel via Chaitin
• Fundamentals of Computation Theory

Cited In (14)

• Information: The Algorithmic Paradigm
• The halting problem is decidable on a set of asymptotic probability one
• Title not available (Why is that?)
• A new perspective on intermediate algorithms via the Riemann-Hilbert correspondence
• Renormalisation and computation. II: Time cut-off and the halting problem
• Anytime Algorithms for Non-Ending Computations
• Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
• A Turing test for free will
• Introduction to the special issue: Computability of the physical
• Computable model discovery and high-level-programming approximations to algorithmic complexity
• Computer Runtimes and the Length of Proofs
• Algorithmic thermodynamics
• Asymptotic behavior and halting probability of Turing machines
• On the generic undecidability of the halting problem for normalized Turing machines

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)