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

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

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

• scientific article; zbMATH DE number 1136091 (Why is no real title available?)
• scientific article; zbMATH DE number 1500663 (Why is no real title available?)
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Algorithmic randomness and complexity.
• Approximations to the halting problem
• Asymptotic proportion of hard instances of the halting problem
• Computability and randomness
• Every 2-random real is Kolmogorov random
• Fundamentals of Computation Theory
• 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
• Fundamentals of Computation Theory
• Most programs stop quickly or never halt
• Algorithmic statistics: forty years later
• Generic algorithms for halting problem and optimal machines revisited

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)