{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,7]],"date-time":"2023-02-07T14:55:45Z","timestamp":1675781745605},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2384,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2007,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not \u2135<jats:sub>0<\/jats:sub>-categorical saturated structure with a unique computable isomor-phism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity. With a variation of this construction, we also provide an example of an \u2135<jats:sub>1<\/jats:sub>-categorical but not \u2135<jats:sub>0<\/jats:sub>-categorical saturated <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200005211_inline1\" \/>-structure with a unique computable isomorphism type. In addition, using the construction we give an example of an \u2135<jats:sub>1<\/jats:sub>-categorical but not \u2135<jats:sub>0<\/jats:sub>-categorical theory whose only non-computable model is the prime one.<\/jats:p>","DOI":"10.2178\/jsl\/1191333855","type":"journal-article","created":{"date-parts":[[2007,12,19]],"date-time":"2007-12-19T16:25:04Z","timestamp":1198081504000},"page":"1041-1054","source":"Crossref","is-referenced-by-count":4,"title":["Applications of Kolmogorov complexity to computable model theory"],"prefix":"10.1017","volume":"72","author":[{"given":"Bakhadyr","family":"Khoussainov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Semukhin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200005211_ref012","volume-title":"Classical recursion theory","author":"Odifreddi","year":"1989"},{"key":"S0022481200005211_ref010","volume-title":"Model theory: an introduction","author":"Marker","year":"2002"},{"key":"S0022481200005211_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"S0022481200005211_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/BF02367027"},{"key":"S0022481200005211_ref004","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"S0022481200005211_ref003","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1143468311"},{"key":"S0022481200005211_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-005-0326-7"},{"key":"S0022481200005211_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04978-5"},{"key":"S0022481200005211_ref011","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0175782-0"},{"key":"S0022481200005211_ref005","volume-title":"A shorter model theory","author":"Hodges","year":"1997"},{"key":"S0022481200005211_ref006","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1305\/ndjfl\/1039724885","article-title":"Computable models of theories with few models","volume":"38","author":"Khoussainov","year":"1997","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"S0022481200005211_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200005211_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(98)00049-9"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200005211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T21:20:25Z","timestamp":1556745625000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200005211\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,9]]}},"alternative-id":["S0022481200005211"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1191333855","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9]]}}}