{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T18:10:18Z","timestamp":1758737418943,"version":"3.44.0"},"reference-count":62,"publisher":"Elsevier","isbn-type":[{"type":"print","value":"9780444898821"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1016\/s0049-237x(99)80023-8","type":"book-chapter","created":{"date-parts":[[2007,9,7]],"date-time":"2007-09-07T16:52:47Z","timestamp":1189183967000},"page":"199-248","source":"Crossref","is-referenced-by-count":2,"title":["An Overview of the Computably Enumerable Sets"],"prefix":"10.1016","member":"78","reference":[{"key":"10.1016\/S0049-237X(99)80023-8_bib1","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01270394","article-title":"Cappable recursively enumerable degrees and Post's program","volume":"32","author":"Ambos-Spies","year":"1992","journal-title":"Arch. Math. Logic"},{"issue":"246","key":"10.1016\/S0049-237X(99)80023-8_bib2","doi-asserted-by":"crossref","DOI":"10.1090\/memo\/0246","article-title":"Decidability and Boolean representations","volume":"32","author":"Burris","year":"1981","journal-title":"Memoirs Amer. Math. Soc"},{"key":"10.1016\/S0049-237X(99)80023-8_bib3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01352931","article-title":"The translation theorem","volume":"33","author":"Cholak","year":"1994","journal-title":"Arch. Math. Logic"},{"issue":"113","key":"10.1016\/S0049-237X(99)80023-8_bib4","article-title":"Automorphisms of the lattice of recursively enumerable sets","author":"Cholak","year":"1995","journal-title":"Mem. Amer. Math. Soc"},{"key":"10.1016\/S0049-237X(99)80023-8_bib5","series-title":"Proceedings of the Oberwolfach Conference on Computability Theory in 1996; Journal of Pure and Applied Logic","article-title":"The dense simple sets are orbit complete,","author":"Cholak","year":"1996"},{"year":"1996","author":"Cholak","journal-title":"A pair of automorphic computably enumerable sets which are not \u03943-automorphic","key":"10.1016\/S0049-237X(99)80023-8_bib6"},{"year":"1992","author":"Cholak","journal-title":"Automorphisms of the computably enumerable sets: the Slaman-Woodin Conjecture, in preparation","key":"10.1016\/S0049-237X(99)80023-8_bib7"},{"key":"10.1016\/S0049-237X(99)80023-8_bib8","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1090\/S0002-9947-1992-1097164-6","article-title":"Automorphisms of the lattice of recursively enumerable sets: Promptly simple sets","volume":"332","author":"Cholak","year":"1992","journal-title":"Trans. Amer. Math. Soc"},{"year":"1936","author":"Cholak","journal-title":"r-maximal sets, in preparation","key":"10.1016\/S0049-237X(99)80023-8_bib9"},{"key":"10.1016\/S0049-237X(99)80023-8_bib10","doi-asserted-by":"crossref","first-page":"345","DOI":"10.2307\/2371045","article-title":"An unsolvable problem of elementary number theory","volume":"58","author":"Church","year":"1936","journal-title":"Amer. J. Math"},{"key":"10.1016\/S0049-237X(99)80023-8_bib11","doi-asserted-by":"crossref","first-page":"40","DOI":"10.2307\/2269326","article-title":"A note on the Entscheidungsproblem","volume":"1","author":"Church","year":"1936","journal-title":"J. Symbolic Logic"},{"year":"1965","author":"Davis","key":"10.1016\/S0049-237X(99)80023-8_bib12"},{"key":"10.1016\/S0049-237X(99)80023-8_bib13","article-title":"There is no fat orbit","author":"Downey","year":"1991","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0001-8708(92)90065-S","article-title":"Automorphisms of the lattice of recursively enumerable sets: Orbits","volume":"92","author":"Downey","year":"1992","journal-title":"Adv. in Math"},{"key":"10.1016\/S0049-237X(99)80023-8_bib15","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1073\/pnas.43.2.236","article-title":"Two recursively enumerable sets of incomparable degrees of unsolvability","volume":"43","author":"Friedberg","year":"1957","journal-title":"Proc. Natl. Acad. Sci. USA"},{"unstructured":"K. GODEL[1934] On undecidable propositions of formal mathematical systems, Notes by S.C. Kleene andBarkley Rosser on lectures at the Institute for Advanced Study, Princeton, NJ; reprinted inDavis [1965], pp. 39-71.","key":"10.1016\/S0049-237X(99)80023-8_bib16"},{"year":"1983","author":"Harrington","journal-title":"The Undecidability of the Lattice of Recursively Enumerable Sets","key":"10.1016\/S0049-237X(99)80023-8_bib17"},{"key":"10.1016\/S0049-237X(99)80023-8_bib18","article-title":"Coding in the lattice of enumerable sets","author":"Harrington","year":"1977","journal-title":"Advances in Math"},{"key":"10.1016\/S0049-237X(99)80023-8_bib19","doi-asserted-by":"crossref","first-page":"10242","DOI":"10.1073\/pnas.88.22.10242","article-title":"Post's Program and incomplete recursively enumerable sets","volume":"88","author":"Harrington","year":"1991","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"10.1016\/S0049-237X(99)80023-8_bib20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511629167.006","article-title":"Dynamic properties of computably enumerable sets","author":"Harrington","year":"1996"},{"key":"10.1016\/S0049-237X(99)80023-8_bib21","doi-asserted-by":"crossref","first-page":"199","DOI":"10.2307\/421110","article-title":"Definability, automorphisms, and dynamic properties of computably enumerable sets","volume":"2","author":"Harrington","year":"1996","journal-title":"Bull. Symbolic Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib22","doi-asserted-by":"crossref","DOI":"10.1090\/S0894-0347-96-00181-6","article-title":"The\n\t\t\t\t\t\t\t\t\u039430 automorphism method and noninvariant classes of degrees","author":"Harrington","year":"1996","journal-title":"J. Amer. Math. Soc"},{"key":"10.1016\/S0049-237X(99)80023-8_bib23","article-title":"Codable sets and orbits of computably enumerable sets","author":"Harrington","year":"1996","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib24","first-page":"97","article-title":"Definable properties of the computably enumerable sets","volume":"94","author":"Harrington","year":"1998"},{"year":"1981","author":"Harrington","journal-title":"Martin's Invariance Conjecture and low sets, in preparation","key":"10.1016\/S0049-237X(99)80023-8_bib25"},{"volume":"36","year":"1981","author":"Herrmann","key":"10.1016\/S0049-237X(99)80023-8_bib26"},{"year":"1983","author":"Herrmann","key":"10.1016\/S0049-237X(99)80023-8_bib27"},{"key":"10.1016\/S0049-237X(99)80023-8_bib28","first-page":"66","article-title":"The undecidability of the elementary theory of the lattice of recursively enumerable sets (abstract)","author":"Herrmann","year":"1984"},{"issue":"5","key":"10.1016\/S0049-237X(99)80023-8_bib29","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1007\/BF01565439","article-title":"General recursive functions of natural numbers","volume":"112","author":"Kleene","year":"1936","journal-title":"Math. Ann"},{"key":"10.1016\/S0049-237X(99)80023-8_bib30","doi-asserted-by":"crossref","first-page":"431","DOI":"10.2307\/2270328","article-title":"Degrees of recursively enumerable sets which have no maximal superset","volume":"33","author":"Lachlan","year":"1968","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib31","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1215\/S0012-7094-68-03513-8","article-title":"The elementary theory of recursively enumerable sets","volume":"35","author":"Lachlan","year":"1968","journal-title":"Duke Math. J"},{"key":"10.1016\/S0049-237X(99)80023-8_bib32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0002-9947-1968-0227009-1","article-title":"On the lattice of recursively enumerable sets","volume":"130","author":"Lachlan","year":"1968","journal-title":"Trans. Amer. Math. Soc"},{"issue":"2","key":"10.1016\/S0049-237X(99)80023-8_bib33","doi-asserted-by":"crossref","first-page":"291","DOI":"10.2307\/1970579","article-title":"On some games which are relevant to the theory of recursively enumerable sets","volume":"91","author":"Lachlan","year":"1970","journal-title":"Ann. of Math"},{"key":"10.1016\/S0049-237X(99)80023-8_bib34","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0003-4843(76)90016-4","article-title":"A recursively enumerable degree which will not split over all lesser ones","volume":"9","author":"Lachlan","year":"1975","journal-title":"Ann. Math. Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib35","doi-asserted-by":"crossref","first-page":"135","DOI":"10.2140\/pjm.1980.87.135","article-title":"d-simple sets, small sets, and degree classes","volume":"87","author":"Lerman","year":"1980","journal-title":"Pacific J. Math"},{"key":"10.1016\/S0049-237X(99)80023-8_bib36","doi-asserted-by":"crossref","first-page":"809","DOI":"10.2307\/2273100","article-title":"Recursively enumerable generic sets","volume":"47","author":"Maass","year":"1982","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib37","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1090\/S0002-9947-1983-0704618-2","article-title":"Characterization of recursively enumerable sets with supersets effectively isomorphic to all recursively enumerable sets","volume":"279","author":"Maass","year":"1983","journal-title":"Trans. Amer. Math. Soc"},{"key":"10.1016\/S0049-237X(99)80023-8_bib38","doi-asserted-by":"crossref","first-page":"51","DOI":"10.2307\/2274090","article-title":"On the orbits of hyperhypersimple sets","volume":"49","author":"Maass","year":"1984","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib39","doi-asserted-by":"crossref","first-page":"138","DOI":"10.2307\/2273796","article-title":"Variations on promptly simple sets","volume":"50","author":"Maass","year":"1985","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib40","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/BF02760850","article-title":"Splitting properties and jump classes","volume":"39","author":"Maass","year":"1981","journal-title":"Israel J. Math"},{"key":"10.1016\/S0049-237X(99)80023-8_bib41","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0168-0072(83)90031-3","article-title":"The interval of the lattice of r.e. sets determined by major subsets","volume":"24","author":"Maass","year":"1983","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib42","first-page":"473","article-title":"A class of incomplete sets","volume":"20","author":"Marchenkov","year":"1976","journal-title":"Mat. Zametki"},{"key":"10.1016\/S0049-237X(99)80023-8_bib43","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1002\/malq.19660120125","article-title":"Classes of recursively enumerable sets and degrees of unsolvability","volume":"12","author":"Martin","year":"1966","journal-title":"Z. Math. Logik Grundlag. Math"},{"year":"1981","author":"Miller","key":"10.1016\/S0049-237X(99)80023-8_bib44"},{"key":"10.1016\/S0049-237X(99)80023-8_bib45","first-page":"194","article-title":"On the unsolvability of the problem of reducibility in the theory of algorithms","volume":"108","author":"Muchnik","year":"1956","journal-title":"Dokl. Akad. Nauk SSR"},{"key":"10.1016\/S0049-237X(99)80023-8_bib46","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1017\/S002248120008525X","article-title":"The lattice of recursively enumerable sets","volume":"21","author":"Myhill","year":"1956","journal-title":"J. Symbolic Logic"},{"year":"1939","author":"Nies","journal-title":"Intervals of the lattice of computably enumerable sets and effective boolean algebras, submitted for publication","key":"10.1016\/S0049-237X(99)80023-8_bib47"},{"key":"10.1016\/S0049-237X(99)80023-8_bib48","doi-asserted-by":"crossref","first-page":"103","DOI":"10.2307\/2269031","article-title":"Finite combinatory processes - formulation I","volume":"1","author":"Post","year":"1936","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib49","doi-asserted-by":"crossref","first-page":"197","DOI":"10.2307\/2371809","article-title":"Formal reductions of the general combinatorial decision problem","volume":"65","author":"Post","year":"1943","journal-title":"Amer. J. Math"},{"key":"10.1016\/S0049-237X(99)80023-8_bib50","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","article-title":"Recursively enumerable sets of positive integers and their decision problems","volume":"50","author":"Post","year":"1944","journal-title":"Bull. Amer. Math. Soc"},{"year":"1967","author":"Rogers","first-page":"482","key":"10.1016\/S0049-237X(99)80023-8_bib51"},{"key":"10.1016\/S0049-237X(99)80023-8_bib52","first-page":"129","article-title":"The theory of Boolean algebras with a distinguished subalgebra is undecidable","volume":"13","author":"Rubin","year":"1976","journal-title":"Ann. Sci. Univ. Clermont-Ferrand II Math"},{"volume":"55","year":"1963","author":"Sacks","key":"10.1016\/S0049-237X(99)80023-8_bib53"},{"key":"10.1016\/S0049-237X(99)80023-8_bib54","doi-asserted-by":"crossref","first-page":"695","DOI":"10.2307\/2272046","article-title":"Degrees of classes of r.e. sets","volume":"41","author":"Shoenfield","year":"1976","journal-title":"J. Symbolic Logic"},{"issue":"2","key":"10.1016\/S0049-237X(99)80023-8_bib55","doi-asserted-by":"crossref","first-page":"80","DOI":"10.2307\/1970842","article-title":"Automorphisms of the recursively enumerable sets, Part I: Maximal sets","volume":"100","author":"Soare","year":"1974","journal-title":"Ann. of Math"},{"key":"10.1016\/S0049-237X(99)80023-8_bib56","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0003-4843(82)90016-X","article-title":"Automorphisms of the lattice of recursively enumerable sets, Part II: Low sets","volume":"22","author":"Soare","year":"1982","journal-title":"Ann. Math. Logic"},{"year":"1987","author":"Soare","key":"10.1016\/S0049-237X(99)80023-8_bib57"},{"key":"10.1016\/S0049-237X(99)80023-8_bib58","doi-asserted-by":"crossref","first-page":"284","DOI":"10.2307\/420992","article-title":"Computability and recursion","volume":"2","author":"Soare","year":"1996","journal-title":"Bull. Symbolic Logic"},{"year":"1996","author":"Soare","article-title":"Computability and enumerability","key":"10.1016\/S0049-237X(99)80023-8_bib59"},{"key":"10.1016\/S0049-237X(99)80023-8_bib60","first-page":"230","article-title":"On computable numbers, with an application to the Entscheidungsproblem","volume":"42","author":"Turing","year":"1936","journal-title":"Proc. London Math. Soc"},{"key":"10.1016\/S0049-237X(99)80023-8_bib61","doi-asserted-by":"crossref","first-page":"153","DOI":"10.2307\/2268280","article-title":"Computability and \u03bb-definability","volume":"2","author":"Turing","year":"1937","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0049-237X(99)80023-8_bib62","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1112\/plms\/s2-45.1.161","article-title":"Systems of logic based on ordinals","volume":"45","author":"Turing","year":"1939","journal-title":"Proc. London Math. Soc"}],"container-title":["Studies in Logic and the Foundations of Mathematics","Handbook of Computability Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0049237X99800238?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0049237X99800238?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T17:32:35Z","timestamp":1758735155000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0049237X99800238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9780444898821"],"references-count":62,"URL":"https:\/\/doi.org\/10.1016\/s0049-237x(99)80023-8","relation":{},"ISSN":["0049-237X"],"issn-type":[{"type":"print","value":"0049-237X"}],"subject":[],"published":{"date-parts":[[1999]]}}}