Most programs stop quickly or never halt

DOI10.1016/j.aam.2007.01.001zbMath1137.68031arXivcs/0610153OpenAlexW2065272524WikidataQ57001609 ScholiaQ57001609MaRDI QIDQ2482913

Cristian S. Calude, Michael A. Stay

Publication date: 28 April 2008

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

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

zbMATH Keywords

halting probabilityhalting problemeffective density

Mathematics Subject Classification ID

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

Related Items

A new perspective on intermediate algorithms via the Riemann-Hilbert correspondence ⋮ Computer Runtimes and the Length of Proofs ⋮ Introduction: computability of the physical ⋮ Renormalisation and computation II: time cut-off and the Halting Problem ⋮ Algorithmic thermodynamics ⋮ Computable model discovery and high-level-programming approximations to algorithmic complexity ⋮ On the generic undecidability of the halting problem for normalized Turing machines ⋮ A Turing test for free will ⋮ Anytime Algorithms for Non-Ending Computations ⋮ Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness ⋮ Information: The Algorithmic Paradigm

Cites Work

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

This page was built for publication: Most programs stop quickly or never halt