{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T21:12:23Z","timestamp":1772831543529,"version":"3.50.1"},"reference-count":43,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3571,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,6]]},"abstract":"<jats:title>Abstract.<\/jats:title><jats:p>We show that the Turing degrees are not sufficient to measure the complexity of continuous functions on [0, 1]. Computability of continuous real functions is a standard notion from computable analysis. However, no satisfactory theory of degrees of continuous functions exists. We introduce the <jats:italic>continuous degrees<\/jats:italic> and prove that they are a proper extension of the Turing degrees and a proper substructure of the enumeration degrees. Call continuous degrees which are not Turing degrees <jats:italic>non-total<\/jats:italic>. Several fundamental results are proved: a continuous function with non-total degree has no least degree representation, settling a question asked by Pour-El and Lempp; every non-computable <jats:italic>f<\/jats:italic> \u2208 <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007908_inline2\"\/>[0,1] computes a non-computable subset of \u2115 there is a non-total degree between Turing degrees <jats:italic>a<\/jats:italic> &lt;<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub><jats:italic>b<\/jats:italic> iff <jats:italic>b<\/jats:italic> is a PA degree relative to <jats:italic>a<\/jats:italic>; <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007908_inline1\"\/> \u2286 2<jats:sup>\u2115<\/jats:sup> is a Scott set iff it is the collection of <jats:italic>f<\/jats:italic>-computable subsets of \u2115 for some <jats:italic>f<\/jats:italic> \u2208 <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007908_inline2\"\/>[0,1] of non-total degree; and there are computably incomparable <jats:italic>f, g<\/jats:italic> \u2208 <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007908_inline2\"\/>[0,1] which compute exactly the same subsets of \u2115. Proofs draw from classical analysis and constructive analysis as well as from computability theory.<\/jats:p>","DOI":"10.2178\/jsl\/1082418543","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T16:38:07Z","timestamp":1109781487000},"page":"555-584","source":"Crossref","is-referenced-by-count":32,"title":["Degrees of unsolvability of continuous functions"],"prefix":"10.1017","volume":"69","author":[{"given":"Joseph S.","family":"Miller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007908_ref031","first-page":"71","volume-title":"Recursive functions (Russian)","author":"Rozinas","year":"1978"},{"key":"S0022481200007908_ref040","first-page":"230","article-title":"On computable numbers, with an application to the Entscheidungsproblem","volume":"42","author":"Turing","year":"1936","journal-title":"Proceedings of the London Mathematical Society. Second Series"},{"key":"S0022481200007908_ref013","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-41-00838-4"},{"key":"S0022481200007908_ref003","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1922-1501192-9"},{"key":"S0022481200007908_ref043","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-56999-9","volume-title":"Computable Analysis, An Introduction","author":"Weihrauch","year":"2000"},{"key":"S0022481200007908_ref024","first-page":"55","article-title":"A constructive map of the square into itself, which moves every constructive point","volume":"152","author":"Orevkov","year":"1963","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200007908_ref035","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19710170139"},{"key":"S0022481200007908_ref036","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71117-0"},{"key":"S0022481200007908_ref005","first-page":"623","volume-title":"Handbook of recursive mathematics","volume":"2","author":"Cenzer","year":"1998"},{"key":"S0022481200007908_ref018","first-page":"129","volume-title":"Constructivity in mathematics:Proceedings of the Colloquium held at Amsterdam, 1957","author":"Lacombe","year":"1959"},{"key":"S0022481200007908_ref033","doi-asserted-by":"publisher","DOI":"10.4064\/sm-2-1-171-180"},{"key":"S0022481200007908_ref025","first-page":"705","volume":"46","author":"Posner","year":"1981","journal-title":"The upper semilattice of degrees \u2264 0\u2032 is complemented"},{"key":"S0022481200007908_ref022","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1961-0125794-X"},{"key":"S0022481200007908_ref017","first-page":"151","article-title":"Extension de la notion de fonction r\u00e9cursive aux fonctions d'une ou plusieurs variables r\u00e9elles. II, III","volume":"241","author":"Lacombe","year":"1955","journal-title":"Comptes Rendus Math\u00e9matique. Acad\u00e9mie des Sciences. Paris"},{"key":"S0022481200007908_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(99)80018-4"},{"key":"S0022481200007908_ref012","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":"S0022481200007908_ref014","volume-title":"Introduction to Metamathematics","author":"Kleene","year":"1952"},{"key":"S0022481200007908_ref021","first-page":"1328","article-title":"On strongand weak reducibility of algorithmic problems","volume":"4","author":"Mu\u010dnik","year":"1963","journal-title":"Akademija Nauk SSSR. Sibirskoe Otdelenie. Sibirski\u012d Matemati\u010deski\u012d \u017durnal"},{"key":"S0022481200007908_ref026","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210102"},{"key":"S0022481200007908_ref028","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21717-7"},{"key":"S0022481200007908_ref023","first-page":"181","volume-title":"The Kleene Symposium (Proceedings of the Symposium, University of Wisconsin, Madison, Wisconsin, 1978)","volume":"101","author":"Nerode","year":"1980"},{"key":"S0022481200007908_ref020","first-page":"501","article-title":"Degrees of difficulty of the mass problem","volume":"104","author":"Medvedev","year":"1955","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200007908_ref029","unstructured":"Richter Linda Jean , Degrees of structures, Ph.D. thesis , University of Illinois at Urbana-Champaign, 1979."},{"key":"S0022481200007908_ref004","first-page":"155","volume-title":"Contributions to the theory of games","author":"Bohnenblust","year":"1950"},{"key":"S0022481200007908_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68952-9"},{"key":"S0022481200007908_ref019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21755-9"},{"key":"S0022481200007908_ref039","doi-asserted-by":"publisher","DOI":"10.2307\/1969604"},{"key":"S0022481200007908_ref042","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90001-A"},{"key":"S0022481200007908_ref001","first-page":"3","article-title":"A criterion for the completeness of recursively enumerable sets, and some generalizations of a fixed point theorem","author":"Arslanov","year":"1977","journal-title":"Izestija Vys\u0161ih U\u010debnyh Zavedeni\u01d0 Matematika"},{"key":"S0022481200007908_ref007","first-page":"854","volume":"47","author":"Cooper","year":"1982","journal-title":"Partial degrees and the density problem"},{"key":"S0022481200007908_ref008","doi-asserted-by":"publisher","DOI":"10.2307\/2371832"},{"key":"S0022481200007908_ref009","doi-asserted-by":"publisher","DOI":"10.4064\/fm-42-1-168-202"},{"key":"S0022481200007908_ref010","doi-asserted-by":"publisher","DOI":"10.4064\/fm-44-1-61-71"},{"key":"S0022481200007908_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90208-7"},{"key":"S0022481200007908_ref016","first-page":"2478","article-title":"Extension de la notion de fonction r\u00e9cursive aux fonctions d'une ou plusieurs variables r\u00e9elles. I","volume":"240","author":"Lacombe","year":"1955","journal-title":"Comptes Rendus Math\u00e9matique. Acad\u00e9mie des Sciences. Paris"},{"key":"S0022481200007908_ref011","unstructured":"Gutteridge Lance , Some results on enumeration reducibility, Ph.D. thesis, Simon Fraser University, 1971."},{"key":"S0022481200007908_ref027","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1983-0682717-1"},{"key":"S0022481200007908_ref037","doi-asserted-by":"publisher","DOI":"10.2307\/1971028"},{"key":"S0022481200007908_ref030","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers","year":"1967"},{"key":"S0022481200007908_ref032","doi-asserted-by":"publisher","DOI":"10.2307\/1970393"},{"key":"S0022481200007908_ref034","first-page":"117","volume-title":"Proceedings of Symposia in Pure Mathematics, Vol. V","author":"Scott","year":"1962"},{"key":"S0022481200007908_ref038","doi-asserted-by":"publisher","DOI":"10.1007\/s001530050064"},{"key":"S0022481200007908_ref041","first-page":"544","article-title":"On computable numbers, with an application to the Entscheidungsproblem. A correction","volume":"43","author":"Turing","year":"1937","journal-title":"Proceedings of the London Mathematical Society. Second Series"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T17:02:32Z","timestamp":1557162152000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007908\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,6]]}},"alternative-id":["S0022481200007908"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1082418543","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,6]]}}}