Generic complexity of undecidable problems
From MaRDI portal
Publication:3503760
DOI10.2178/jsl/1208359065zbMath1140.03025MaRDI QIDQ3503760
Alexander N. Rybalov, Alexei G. Myasnikov
Publication date: 9 June 2008
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2178/jsl/1208359065
word problem; finitely presented semigroups; Rice theorem; generic amplification; absolutely undecidable problems; generic immune sets; strong undecidability; super-undecidable problems
20M05: Free semigroups, generators and relations, word problems
03D35: Undecidability and degrees of sets of sentences
Related Items
ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS, Algorithmically finite groups., On mathematical contributions of Paul E. Schupp, Exponentially generic subsets of groups, Random equations in free groups, Expander graphs in pure and applied mathematics
Cites Work
- Unnamed Item
- Average-case complexity and decision problems in group theory.
- 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
- MULTIPLICATIVE MEASURES ON FREE GROUPS
- Recursive Unsolvability of a problem of Thue