What Percentage of Programs Halt?
From MaRDI portal
Publication:3448787
DOI10.1007/978-3-662-47672-7_18zbMath1440.03057OpenAlexW1044326647WikidataQ57349433 ScholiaQ57349433MaRDI QIDQ3448787
Laurent Bienvenu, Alexander Shen, Damien Desfontaines
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
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Turing machines and related notions (03D10) Algorithmic randomness and dimension (03D32)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Universal recursively enumerable sets of strings
- Approximations to the halting problem
- Limit complexities revisited
- The halting problem is decidable on a set of asymptotic probability one
- Randomness and Recursive Enumerability
- Random Semicomputable Reals Revisited
- Asymptotic Proportion of Hard Instances of the Halting Problem
- Algorithmic Randomness and Complexity
- Optimal enumerations and optimal gödel numberings
- Every 2-random real is Kolmogorov random
- ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
- Fundamentals of Computation Theory