{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T15:23:53Z","timestamp":1775834633662,"version":"3.50.1"},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T00:00:00Z","timestamp":1389744000000},"content-version":"unspecified","delay-in-days":4976,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[2000,6]]},"abstract":"<jats:p>There has been increasing interest over the last few decades in the study of the effective content of Mathematics. One field whose effective content has been the subject of a large body of work, dating back at least to the early 1960s, is model theory. (A valuable reference is the handbook [7]. In particular, the introduction and the articles by Ershov and Goncharov and by Harizanov give useful overviews, while the articles by Ash and by Goncharov cover material related to the topic of this communication.)<\/jats:p><jats:p>Several different notions of effectiveness of model-theoretic structures have been investigated. This communication is concerned with<jats:italic>computable<\/jats:italic>structures, that is, structures with computable domains whose constants, functions, and relations are uniformly computable.<\/jats:p><jats:p>In model theory, we identify isomorphic structures. From the point of view of computable model theory, however, two isomorphic structures might be very different. For example, under the standard ordering of \u03c9 the success or relation is computable, but it is not hard to construct a computable linear ordering of type \u03c9 in which the successor relation is not computable. In fact, for every computably enumerable (c. e.) degree a, we can construct a computable linear ordering of type \u03c9 in which the successor relation has degree a. It is also possible to build two isomorphic computable groups, only one of which has a computable center, or two isomorphic Boolean algebras, only one of which has a computable set of atoms. Thus, for the purposes of computable model theory, studying structures up to isomorphism is not enough.<\/jats:p>","DOI":"10.2307\/421207","type":"journal-article","created":{"date-parts":[[2006,5,7]],"date-time":"2006-05-07T07:13:57Z","timestamp":1146986037000},"page":"197-212","source":"Crossref","is-referenced-by-count":9,"title":["Degree Spectra of Relations on Computable Structures"],"prefix":"10.1017","volume":"6","author":[{"given":"Denis R.","family":"Hirschfeldt","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600006582_ref031","doi-asserted-by":"publisher","DOI":"10.1007\/BF01463352"},{"key":"S1079898600006582_ref002","first-page":"26","volume-title":"Aspects of effective algebra (Clayton, 1979)","author":"Ash","year":"1981"},{"key":"S1079898600006582_ref013","volume-title":"Countable boolean algebras and decidability","author":"Goncharov","year":"1997"},{"key":"S1079898600006582_ref021","article-title":"Degree spectra of intrinsically c. e. relations","author":"Hirschfeldt","journal-title":"Journal of Symbolic Logic"},{"key":"S1079898600006582_ref014","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669102"},{"key":"S1079898600006582_ref006","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/BFb0090937","volume-title":"Logic year 1979\u201380 (Proceedings of Seminars and Conferences in Mathematical Logic, University of Connecticut, Storrs, Connecticut, 1979\/80)","volume":"859","author":"Epstein","year":"1981"},{"key":"S1079898600006582_ref028","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(79)90011-1"},{"key":"S1079898600006582_ref026","unstructured":"Kudinov O. , An integral domain with finite algorithmic dimension, personal communication."},{"key":"S1079898600006582_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669323"},{"key":"S1079898600006582_ref033","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S1079898600006582_ref030","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19860322514"},{"key":"S1079898600006582_ref017","unstructured":"Harizanov V. S. , Degree spectrum of a recursive relation on a recursive structure, Ph.D. Thesis , University of Wisconsin, Madison, WI, 1987."},{"key":"S1079898600006582_ref016","doi-asserted-by":"publisher","DOI":"10.1007\/BF01054216"},{"key":"S1079898600006582_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669607"},{"key":"S1079898600006582_ref007","volume-title":"Handbook of recursive mathematics","volume":"139","author":"Ershov","year":"1998"},{"key":"S1079898600006582_ref004","doi-asserted-by":"publisher","DOI":"10.2307\/2586747"},{"key":"S1079898600006582_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(96)00011-5"},{"key":"S1079898600006582_ref019","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90190-O"},{"key":"S1079898600006582_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90097-6"},{"key":"S1079898600006582_ref011","first-page":"58","article-title":"Groups with a finite number of constructivizations","volume":"23","author":"Goncharov","year":"1981","journal-title":"Soviet Math.Dokl."},{"key":"S1079898600006582_ref032","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1981-0624937-1"},{"key":"S1079898600006582_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669456"},{"key":"S1079898600006582_ref025","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00059-6"},{"key":"S1079898600006582_ref022","unstructured":"Hirschfeldt D. R. , Khoussainov B. , Shore R. A. , and Slinko A. M. , Degree spectra and computable dimension in algebraic structures, to appear."},{"key":"S1079898600006582_ref029","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200031297"},{"key":"S1079898600006582_ref020","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00056-0"},{"key":"S1079898600006582_ref024","volume-title":"Dokl. Akad. Nauk SSSR","author":"Khoussainov"},{"key":"S1079898600006582_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90005-7"},{"key":"S1079898600006582_ref015","first-page":"55","article-title":"On the spectrum of degrees of decidable relations","volume":"55","author":"Goncharov","year":"1997","journal-title":"Doklady Math."},{"key":"S1079898600006582_ref027","first-page":"552","article-title":"Recursively represented Boolean algebras","volume":"24","author":"LaRoche","year":"1977","journal-title":"Notices of the American Mathematical Society"},{"key":"S1079898600006582_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(88)90014-0"},{"key":"S1079898600006582_ref012","first-page":"4","volume-title":"Mathematical logic and the theory of algorithms","author":"Goncharov","year":"1982"},{"key":"S1079898600006582_ref023","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600006582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T14:34:11Z","timestamp":1586874851000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600006582\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,6]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,6]]}},"alternative-id":["S1079898600006582"],"URL":"https:\/\/doi.org\/10.2307\/421207","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,6]]}}}