Generic Complexity of Undecidable Problems

DOI10.1007/978-3-540-74510-5_41zbMATH Open1188.03027OpenAlexW1536365843MaRDI QIDQ3499790FDOQ3499790

Authors: Alexei Myasnikov 

Publication date: 3 June 2008

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74510-5_41

Recommendations

• Generic complexity of undecidable problems
• On the strongly generic undecidability of the halting problem
• Generic undecidability of universal theories
• Generic amplification of recursively enumerable sets
• On the generic undecidability of the halting problem for normalized Turing machines

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35)

Cited In (4)

• Undecidability in Some Structures Related to Computation Theory
• Title not available (Why is that?)
• On the strongly generic undecidability of the halting problem
• Generic complexity of undecidable problems

This page was built for publication: Generic Complexity of Undecidable Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499790)