{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,24]],"date-time":"2024-02-24T12:10:04Z","timestamp":1708776604755},"reference-count":80,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":4063,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[2002,12]]},"abstract":"<jats:p>Computable model theory, also called effective or recursive model theory, studies algorithmic properties of mathematical structures, their relations, and isomorphisms. These properties can be described syntactically or semantically. One of the major tasks of computable model theory is to obtain, whenever possible, computability-theoretic versions of various classical model-theoretic notions and results. For example, in the 1950's, Fr\u00f6hlich and Shepherdson realized that the concept of a computable function can make van der Waerden's intuitive notion of an<jats:italic>explicit<\/jats:italic>field precise. This led to the notion of a<jats:italic>computable<\/jats:italic>structure. In 1960, Rabin proved that every computable field has a computable algebraic closure. However, not every classical result \u201ceffectivizes\u201d. Unlike Vaught's theorem that no complete theory has exactly two nonisomorphic countable models, Millar's and Kudaibergenov's result establishes that there is a complete decidable theory that has<jats:italic>exactly two<\/jats:italic>nonisomorphic countable models with computable elementary diagrams. In the 1970's, Metakides and Nerode [58], [59] and Remmel [71], [72], [73] used more advanced methods of computability theory to investigate algorithmic properties of fields, vector spaces, and other mathematical structures.<\/jats:p>","DOI":"10.2178\/bsl\/1182353917","type":"journal-article","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T17:10:15Z","timestamp":1207242615000},"page":"457-477","source":"Crossref","is-referenced-by-count":8,"title":["Computability-Theoretic Complexity of Countable Structures"],"prefix":"10.1017","volume":"8","author":[{"given":"Valentina S.","family":"Harizanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S107989860000843X_ref038","first-page":"33","article-title":"classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"},{"key":"S107989860000843X_ref013","unstructured":"Csima B. F. , Computability of prime and saturated models, Ph.D. thesis , University of Chicago, in preparation."},{"key":"S107989860000843X_ref062","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(78)90030-X"},{"key":"S107989860000843X_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4305-3"},{"key":"S107989860000843X_ref035","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-01-05923-8"},{"key":"S107989860000843X_ref066","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(84)90028-9"},{"key":"S107989860000843X_ref049","doi-asserted-by":"publisher","DOI":"10.2307\/2695117"},{"key":"S107989860000843X_ref064","doi-asserted-by":"publisher","DOI":"10.2307\/2695025"},{"key":"S107989860000843X_ref040","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198532132.001.0001","volume-title":"Models of Peano Arithmetic","author":"Kaye","year":"1991"},{"key":"S107989860000843X_ref018","first-page":"157","volume-title":"Complexity, logic, and recursion theory","author":"Downey","year":"1997"},{"key":"S107989860000843X_ref054","doi-asserted-by":"publisher","DOI":"10.2307\/2273704"},{"key":"S107989860000843X_ref016","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1994-1203984-4"},{"key":"S107989860000843X_ref042","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":"S107989860000843X_ref068","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1305\/ndjfl\/1022615611","article-title":"A new spectrum of recursive models","volume":"40","author":"Nies","year":"1999","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"S107989860000843X_ref052","doi-asserted-by":"publisher","DOI":"10.2307\/2275921"},{"key":"S107989860000843X_ref011","doi-asserted-by":"publisher","DOI":"10.2307\/2274481"},{"key":"S107989860000843X_ref055","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1984-0732105-5"},{"key":"S107989860000843X_ref053","doi-asserted-by":"publisher","DOI":"10.2307\/2586587"},{"key":"S107989860000843X_ref048","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511565670.011"},{"key":"S107989860000843X_ref001","unstructured":"Arana A. , Possible m-diagrams of models of arithmetic, to appear in a volume on reverse mathematics (S. G. Simpson, editor)."},{"key":"S107989860000843X_ref056","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71887-1"},{"key":"S107989860000843X_ref036","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00087-2"},{"key":"S107989860000843X_ref074","doi-asserted-by":"publisher","DOI":"10.2307\/2273222"},{"key":"S107989860000843X_ref010","volume-title":"Model theory","author":"Chang","year":"1990"},{"key":"S107989860000843X_ref028","volume-title":"Algebra and Logic","author":"Goncharov"},{"key":"S107989860000843X_ref004","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1990-0955487-0"},{"key":"S107989860000843X_ref023","doi-asserted-by":"publisher","DOI":"10.1007\/BF01431432"},{"key":"S107989860000843X_ref029","doi-asserted-by":"publisher","DOI":"10.1007\/BF02219289"},{"key":"S107989860000843X_ref058","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(77)90015-8"},{"key":"S107989860000843X_ref069","doi-asserted-by":"publisher","DOI":"10.1007\/BF01980636"},{"key":"S107989860000843X_ref017","first-page":"545","article-title":"Orderings with \u03b1th jump degree 0 (\u03b1)","volume":"114","author":"Downey","year":"1992","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S107989860000843X_ref057","doi-asserted-by":"publisher","DOI":"10.2307\/2274752"},{"key":"S107989860000843X_ref012","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1305\/ndjfl\/1039118866","article-title":"An undecidable linear order that is n-decidable for all n","volume":"39","author":"Chisholm","year":"1998","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"S107989860000843X_ref034","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-99-04920-5"},{"key":"S107989860000843X_ref065","doi-asserted-by":"publisher","DOI":"10.1007\/BF02757002"},{"key":"S107989860000843X_ref019","volume-title":"Decidability problems and constructive models","author":"Ershov","year":"1980"},{"key":"S107989860000843X_ref077","doi-asserted-by":"publisher","DOI":"10.2307\/3062109"},{"key":"S107989860000843X_ref014","first-page":"14","article-title":"Degree spectra of prime models","volume":"23","author":"Csima","year":"2002","journal-title":"Abstracts of papers presented to the American Mathematical Society"},{"key":"S107989860000843X_ref031","first-page":"3","volume-title":"Handbook of recursive mathematics","volume":"1","author":"Harizanov","year":"1998"},{"key":"S107989860000843X_ref030","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90097-6"},{"key":"S107989860000843X_ref063","first-page":"507","volume-title":"Handbook of computability theory","author":"Metakides","year":"1999"},{"key":"S107989860000843X_ref022","first-page":"601","article-title":"Restricted theories of constructive Boolean algebras","volume":"17","author":"Goncharov","year":"1976","journal-title":"Sibirskii Matematicheskii Zhurnal"},{"key":"S107989860000843X_ref027","volume-title":"Proceedings of the American Mathematical Society","author":"Goncharov"},{"key":"S107989860000843X_ref067","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0325-4_19"},{"key":"S107989860000843X_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00095-1"},{"key":"S107989860000843X_ref037","doi-asserted-by":"publisher","DOI":"10.2307\/2275695"},{"key":"S107989860000843X_ref021","first-page":"679","article-title":"Arithmetically definable models of formalized arithmetic","volume":"5","author":"Feferman","year":"1958","journal-title":"Notices of the American Mathematical Society"},{"key":"S107989860000843X_ref047","doi-asserted-by":"publisher","DOI":"10.2307\/2273915"},{"key":"S107989860000843X_ref044","doi-asserted-by":"publisher","DOI":"10.2307\/2274174"},{"key":"S107989860000843X_ref008","first-page":"5","volume-title":"Studies in model theory","author":"Barwise","year":"1973"},{"key":"S107989860000843X_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90015-8"},{"key":"S107989860000843X_ref080","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-98-04314-7"},{"key":"S107989860000843X_ref045","unstructured":"Knight J. F. , Models of arithmetic: quantifiers and complexity, (S. G. Simpson, editor), to appear in a volume on reverse mathematics."},{"key":"S107989860000843X_ref015","unstructured":"Csima B. F. , Hirschfeldt D. R. , Knight J. F. , and Soare R. I. , Bounding prime models, preprint."},{"key":"S107989860000843X_ref046","unstructured":"Knight J. F. , Sequences of degrees associated with models of arithmetic, to appear in a volume on Logic Colloquium 2001."},{"key":"S107989860000843X_ref073","doi-asserted-by":"publisher","DOI":"10.2307\/2273757"},{"key":"S107989860000843X_ref025","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669834"},{"key":"S107989860000843X_ref039","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90038-N"},{"key":"S107989860000843X_ref071","doi-asserted-by":"publisher","DOI":"10.2307\/2272868"},{"key":"S107989860000843X_ref032","article-title":"Sequences of n-diagrams","author":"Harizanov","journal-title":"The Journal of Symbolic Logic"},{"key":"S107989860000843X_ref051","first-page":"155","article-title":"Constructivizable models of undecidable theories","volume":"21","author":"Kudaibergenov","year":"1980","journal-title":"Siberian Mathematical Journal"},{"key":"S107989860000843X_ref079","first-page":"3859","article-title":"Every low2 Boolean algebra has a recursive copy","volume":"123","author":"Thurber","year":"1995","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S107989860000843X_ref059","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(79)90011-1"},{"key":"S107989860000843X_ref041","first-page":"83","article-title":"On strongly constructive models of a decidable theory","volume":"35","author":"Khisamiev","year":"1974","journal-title":"Izvestii Akademii Nauk Kazakhstan SSR"},{"key":"S107989860000843X_ref061","doi-asserted-by":"crossref","first-page":"171","DOI":"10.2307\/2273331","article-title":"Omitting types, type spectrums, and decidability","volume":"48","author":"Metakides","year":"1983","journal-title":"The Journal of Symbolic Logic"},{"key":"S107989860000843X_ref072","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(78)90027-X"},{"key":"S107989860000843X_ref076","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-98-04307-X"},{"key":"S107989860000843X_ref024","doi-asserted-by":"publisher","DOI":"10.1007\/BF01674776"},{"key":"S107989860000843X_ref007","first-page":"26","volume-title":"Aspects of effective algebra","author":"Ash","year":"1981"},{"key":"S107989860000843X_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(96)00026-7"},{"key":"S107989860000843X_ref075","first-page":"117","volume-title":"Proceedings of the fifth symposium in pure mathematics","author":"Scott","year":"1962"},{"key":"S107989860000843X_ref006","volume-title":"Computable structures and the hyperarithmetical hierarchy","author":"Ash","year":"2000"},{"key":"S107989860000843X_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-80177-8"},{"key":"S107989860000843X_ref026","volume-title":"Countable Boolean algebras and decidability","author":"Goncharov","year":"1997"},{"key":"S107989860000843X_ref060","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1980.91.407"},{"key":"S107989860000843X_ref050","doi-asserted-by":"publisher","DOI":"10.2307\/2695066"},{"key":"S107989860000843X_ref070","doi-asserted-by":"publisher","DOI":"10.1007\/BF01674780"},{"key":"S107989860000843X_ref078","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S107989860000843X_ref033","doi-asserted-by":"publisher","DOI":"10.2307\/2272643"},{"key":"S107989860000843X_ref043","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511565670.009"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S107989860000843X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,24]],"date-time":"2024-02-24T11:54:32Z","timestamp":1708775672000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S107989860000843X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,12]]},"references-count":80,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2002,12]]}},"alternative-id":["S107989860000843X"],"URL":"https:\/\/doi.org\/10.2178\/bsl\/1182353917","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,12]]}}}