On the strongly generic undecidability of the halting problem

DOI10.1016/j.tcs.2007.02.010zbMath1118.03033OpenAlexW1983360706MaRDI QIDQ884482

Alexander N. Rybalov

Publication date: 6 June 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.010

zbMATH Keywords

halting problemgeneric complexity

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Turing machines and related notions (03D10)

Related Items

Asymptotic density, immunity and randomness, On the generic undecidability of the halting problem for normalized Turing machines, Generic complexity of undecidable problems, Generic amplification of recursively enumerable sets, The generic complexity of the bounded problem of graphs clustering, The generic complexity of the graph triangulation problem

Cites Work

• Average-case complexity and decision problems in group theory.
• Generic-case complexity, decision problems in group theory, and random walks.
• The halting problem is decidable on a set of asymptotic probability one
• MULTIPLICATIVE MEASURES ON FREE GROUPS