On the generic undecidability of the halting problem for normalized Turing machines
From MaRDI portal
Publication:2398210
DOI10.1007/s00224-016-9698-9zbMath1369.03115OpenAlexW2464573758MaRDI QIDQ2398210
Publication date: 15 August 2017
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-016-9698-9
Cites Work
- On the strongly generic undecidability of the halting problem
- Generic-case complexity, decision problems in group theory, and random walks.
- The halting problem is decidable on a set of asymptotic probability one
- Most programs stop quickly or never halt
- A Theory of Program Size Formally Identical to Information Theory