What percentage of programs halt?

DOI10.1007/978-3-662-47672-7_18MaRDI QIDQ3448787zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Laurent Bienvenu, Damien Desfontaines, A. Shen

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://zenodo.org/record/51938

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Algorithmic randomness and dimension (03D32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Generic algorithms for halting problem and optimal machines revisited
• The halting problem is decidable on a set of asymptotic probability one
• Randomness and halting probabilities
• Most programs stop quickly or never halt
• Fundamentals of Computation Theory

Cites work

• Algorithmic randomness and complexity.
• Approximations to the halting problem
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Asymptotic proportion of hard instances of the halting problem
• Computability and randomness
• Every 2-random real is Kolmogorov random
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 1136091 (Why is no real title available?)
• scientific article; zbMATH DE number 1500663 (Why is no real title available?)
• Limit complexities revisited
• Optimal enumerations and optimal gödel numberings
• Random semicomputable reals revisited
• Randomness and recursive enumerability
• The halting problem is decidable on a set of asymptotic probability one
• Universal recursively enumerable sets of strings

Cited in

(5)

• The halting problem is decidable on a set of asymptotic probability one
• Most programs stop quickly or never halt
• Generic algorithms for halting problem and optimal machines revisited
• Algorithmic statistics: forty years later
• Fundamentals of Computation Theory

This page was built for publication: What percentage of programs halt?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448787)