{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T17:22:14Z","timestamp":1709832134757},"reference-count":33,"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":6254,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log."],"published-print":{"date-parts":[[1996,12]]},"abstract":"<jats:p><jats:bold>\u00a71. Introduction<\/jats:bold>. Natural sets that can be enumerated by a computable function (the <jats:italic>recursively enumerable<\/jats:italic> or <jats:italic>r.e. sets<\/jats:italic>) always seem to be either actually computable (<jats:italic>recursive<\/jats:italic>) or of the same complexity (with respect to Turing computability) as the Halting Problem, the complete r.e. set <jats:italic>K<\/jats:italic>. The obvious question, first posed in Post [1944] and since then called <jats:italic>Post's Problem<\/jats:italic> is then just whether there are r.e. sets which are neither computable nor complete, i.e., neither recursive nor of the same Turing degree as <jats:italic>K<\/jats:italic>?<\/jats:p><jats:p>Let <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600007721_inline1\" \/> be the r.e. degrees, i.e., the r.e. sets modulo the equivalence relation of equicomputable with the partial order induced by Turing computability. This structure is a partial order (indeed, an uppersemilattice or <jats:italic>usl<\/jats:italic>)with least element <jats:bold>0<\/jats:bold>, the degree (equivalence class) of the computable sets, and greatest element <jats:bold>1<\/jats:bold> or <jats:bold>0<\/jats:bold>\u2032, the degree of <jats:italic>K<\/jats:italic>. Post's problem then asks if there are any other elements of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600007721_inline2\" \/>.<\/jats:p><jats:p>The (positive) solution of Post's problem by Friedberg [1957] and Muchnik [1956] was followed by various algebraic or order theoretic results that were interpreted as saying that the structure <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600007721_inline3\" \/> was in some way well behaved:<\/jats:p><jats:p>T<jats:sc>heorem<\/jats:sc> 1.1 (Embedding theorem; Muchnik [1958], Sacks [1963]). <jats:italic>Every countable partial ordering or even uppersemilattice can be embedded into <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1079898600007721_inline4\" \/><\/jats:italic>.<\/jats:p><jats:p>T<jats:sc>heorem<\/jats:sc> 1.2 (Sacks Splitting Theorem [1963b]). <jats:italic>For every nonrecursive r.e. degree<\/jats:italic><jats:bold>a<\/jats:bold><jats:italic>there are r.e. degrees<\/jats:italic><jats:bold>b, c<\/jats:bold> &lt; <jats:bold>a<\/jats:bold><jats:italic>such that<\/jats:italic><jats:bold>b<\/jats:bold> \u2228 <jats:bold>c<\/jats:bold> = <jats:bold>a<\/jats:bold>.<\/jats:p><jats:p>T<jats:sc>heorem<\/jats:sc> 1.3 (Sacks Density Theorem [1964]). <jats:italic>For every pair of nonrecursive r.e. degrees<\/jats:italic><jats:bold>a<\/jats:bold> &lt; <jats:bold>b<\/jats:bold><jats:italic>there is an r.e. degree<\/jats:italic><jats:bold>c<\/jats:bold><jats:italic>such that<\/jats:italic><jats:bold>a<\/jats:bold> &lt; <jats:bold>c<\/jats:bold> &lt; <jats:bold>b<\/jats:bold>.<\/jats:p>","DOI":"10.2307\/421171","type":"journal-article","created":{"date-parts":[[2006,5,7]],"date-time":"2006-05-07T07:09:31Z","timestamp":1146985771000},"page":"392-404","source":"Crossref","is-referenced-by-count":8,"title":["Definability in the Recursively Enumerable Degrees"],"prefix":"10.1017","volume":"2","author":[{"given":"Andr\u00e9","family":"Nies","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard A.","family":"Shore","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theodore A.","family":"Slaman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,1,15]]},"reference":[{"key":"S1079898600007721_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(80)90027-4"},{"key":"S1079898600007721_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(76)90016-4"},{"key":"S1079898600007721_ref006","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1982-14970-9"},{"key":"S1079898600007721_ref015","first-page":"391","article-title":"Solution of Post's reduction problem and of certain other problems in the theory of algorithms","volume":"7","author":"Muchnik","year":"1958","journal-title":"Trudy Moskovskogo Matematicheskogo Obshchestva"},{"key":"S1079898600007721_ref027","first-page":"256","article-title":"Finitely generated codings and the degrees r.e. in a degree d","volume":"84","author":"Shore","year":"1982","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S1079898600007721_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90206-S"},{"key":"S1079898600007721_ref031","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S1079898600007721_ref032","unstructured":"[1988] Weinstein B. J. , On embeddings of the 1-3-1 into the recursively enumerable degrees, Ph.D. thesis , University of California, Berkeley."},{"key":"S1079898600007721_ref021","doi-asserted-by":"publisher","DOI":"10.2307\/1970214"},{"key":"S1079898600007721_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90062-7"},{"key":"S1079898600007721_ref001","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1984-0719661-8"},{"key":"S1079898600007721_ref011","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0059544"},{"key":"S1079898600007721_ref009","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-16.1.537"},{"key":"S1079898600007721_ref019","volume-title":"Annals of Mathematics Studies","volume":"55","author":"Sacks","year":"1963"},{"key":"S1079898600007721_ref017","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1944-08111-1"},{"key":"S1079898600007721_ref020","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1963-0155747-3"},{"key":"S1079898600007721_ref026","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-24.1.1"},{"key":"S1079898600007721_ref008","first-page":"599","article-title":"Pseudo-jump operators I: the r.e. case","volume":"275","author":"Jockusch","year":"1983","journal-title":"Transactions ofthe American Mathematical Society"},{"key":"S1079898600007721_ref028","doi-asserted-by":"publisher","DOI":"10.2307\/2273376"},{"key":"S1079898600007721_ref003","volume-title":"Beyond G\u00f6del's theorem: the failure to capture information content","author":"Cooper","year":"1996"},{"key":"S1079898600007721_ref018","doi-asserted-by":"publisher","DOI":"10.2307\/1970776"},{"key":"S1079898600007721_ref010","doi-asserted-by":"publisher","DOI":"10.2307\/2270459"},{"key":"S1079898600007721_ref014","first-page":"29","article-title":"On the unsolvability of the problem of reducibility in the theory of algorithms","volume":"108","author":"Muchnik","year":"1956","journal-title":"Doklady Akademiya Nauk SSSR, New Series"},{"key":"S1079898600007721_ref030","first-page":"303","volume-title":"Proceedings of the International Congress on Mathematics, Kyoto 1990","author":"Slaman","year":"1991"},{"key":"S1079898600007721_ref007","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"S1079898600007721_ref016","unstructured":"[1992] Nies A. , Definability and undecidability in recursion theoretic semilattices, Ph.D. thesis , Universit\u00e4t Heidelberg."},{"key":"S1079898600007721_ref023","volume-title":"Annals of Mathematics Studies","volume":"55","author":"Sacks","year":"1966"},{"key":"S1079898600007721_ref025","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.76.9.4218"},{"key":"S1079898600007721_ref024","first-page":"359","volume-title":"Symposium on the theory ofmodels","author":"Shoenfield","year":"1965"},{"key":"S1079898600007721_ref029","doi-asserted-by":"publisher","DOI":"10.1007\/BF01621095"},{"key":"S1079898600007721_ref033","doi-asserted-by":"publisher","DOI":"10.2307\/2269807"},{"key":"S1079898600007721_ref005","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.43.2.236"},{"key":"S1079898600007721_ref022","doi-asserted-by":"publisher","DOI":"10.2307\/1970393"}],"container-title":["Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600007721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T19:47:59Z","timestamp":1557690479000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600007721\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["S1079898600007721"],"URL":"https:\/\/doi.org\/10.2307\/421171","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}