{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T00:03:16Z","timestamp":1770336196035,"version":"3.49.0"},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2110,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we study generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are undecidable on every strongly generic subset of inputs. For instance, the classical Halting Problem is strongly undecidable. Moreover, we prove an analog of the Rice theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. Then we show that there are natural super-undecidable problems, i.e., problem which are undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introduce a method of generic amplification (an analog of the amplification in complexity theory). Finally, we construct absolutely undecidable problems, which stay undecidable on every non-negligible set of inputs. Their construction rests on generic immune sets.<\/jats:p>","DOI":"10.2178\/jsl\/1208359065","type":"journal-article","created":{"date-parts":[[2008,4,16]],"date-time":"2008-04-16T19:50:47Z","timestamp":1208375447000},"page":"656-673","source":"Crossref","is-referenced-by-count":23,"title":["Generic complexity of undecidable problems"],"prefix":"10.1017","volume":"73","author":[{"given":"Alexei G.","family":"Myasnikov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander N.","family":"Rybalov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200004552_ref018","first-page":"172","article-title":"An associative system with undecidable equivalence problem","volume":"52","author":"Tseitin","year":"1958","journal-title":"Reports of Mathematical Institute of Soviet Academy of Science"},{"key":"S0022481200004552_ref017","volume-title":"The Complexity of Computing","author":"Savage","year":"1977"},{"key":"S0022481200004552_ref014","unstructured":"Miasnikov A. , Ushakov A. , and Won D. W. , Generic complexity of the word problem in finitely presented semigroups, 2006, preprint."},{"key":"S0022481200004552_ref013","volume-title":"Introduction to Mathematical Logic","author":"Mendflson","year":"1997"},{"key":"S0022481200004552_ref012","first-page":"1264","article-title":"Simple examples of undecidable associative calculi","volume":"173","author":"Matiyasevich","year":"1967","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200004552_ref011","first-page":"587","article-title":"On the impossibility of certain algorithms in the theory of associative systems","volume":"55","author":"Markov","year":"1947","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200004552_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2003.02.001"},{"key":"S0022481200004552_ref006","unstructured":"Gilman R. , Miasnikov A. D. , Myasnikov A. G. , and Ushakov A. , Generic complexity, preprint."},{"key":"S0022481200004552_ref005","volume-title":"Computability Ttheory","author":"Cooper","year":"2003"},{"key":"S0022481200004552_ref003","article-title":"Algorithmic stratification of the conjugacy problem in Miller's groups","author":"Borovik","journal-title":"International Journal of Algebra and Computation"},{"key":"S0022481200004552_ref002","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196703001596"},{"key":"S0022481200004552_ref004","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/298\/05112"},{"key":"S0022481200004552_ref001","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1070\/RM2000v055n02ABEH000267","article-title":"Decision problems for groups and semigroups","volume":"55","author":"Adjan","year":"2000","journal-title":"Russian Mathematical Surveys"},{"key":"S0022481200004552_ref007","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1168352664"},{"key":"S0022481200004552_ref010","volume-title":"The Art of Computer Programming. Vol.3: Sorting and Searching","author":"Knuth","year":"1998"},{"key":"S0022481200004552_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.010"},{"key":"S0022481200004552_ref015","first-page":"1","volume":"12","author":"Post","year":"1947","journal-title":"Recursive unsolvability of a problem of Thue"},{"key":"S0022481200004552_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-8693(03)00167-4"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200004552","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T23:32:15Z","timestamp":1556667135000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200004552\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["S0022481200004552"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1208359065","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}