{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:57:42Z","timestamp":1747173462548,"version":"3.40.5"},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T00:00:00Z","timestamp":1727049600000},"content-version":"unspecified","delay-in-days":114,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We discuss the complexity of completions of partial combinatory algebras, in particular, of Kleene\u2019s first model. Various completions of this model exist in the literature, but all of them have high complexity. We show that although there are no computable completions, there exist completions of low Turing degree. We use this construction to relate completions of Kleene\u2019s first model to complete extensions of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000252_inline1.png\"\/><jats:tex-math>\n$\\mathrm{PA}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We also discuss the complexity of pcas defined from nonstandard models of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000252_inline2.png\"\/><jats:tex-math>\n$\\mathrm{PA}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0960129524000252","type":"journal-article","created":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T11:32:32Z","timestamp":1727091152000},"page":"455-466","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["The complexity of completions in partial combinatory algebra"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1464-6908","authenticated-orcid":false,"given":"Sebastiaan","family":"Terwijn","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2024,9,23]]},"reference":[{"key":"S0960129524000252_ref28","doi-asserted-by":"publisher","DOI":"10.1201\/9781439865835-14"},{"key":"S0960129524000252_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90050-3"},{"key":"S0960129524000252_ref33","unstructured":"Terwijn, S. A. (2023). Completions of Kleene\u2019s second model, arXiv."},{"key":"S0960129524000252_ref38","unstructured":"Zoethout, J. (2022). Computability Models and Realizability Toposes. Phd thesis, Utrecht University."},{"key":"S0960129524000252_ref1","doi-asserted-by":"publisher","DOI":"10.2307\/2275638"},{"key":"S0960129524000252_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129599002832"},{"key":"S0960129524000252_ref15","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exaa087"},{"key":"S0960129524000252_ref17","first-page":"35","article-title":"$\\Pi^0_1$\n\n\n-classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0960129524000252_ref19","unstructured":"Kihara, T. (2022). Rethinking the notion of oracle, preprint, arXiv."},{"key":"S0960129524000252_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68952-9"},{"key":"S0960129524000252_ref36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511565670.019"},{"key":"S0960129524000252_ref2","volume-title":"The Lambda Calculus","volume":"103","author":"Barendregt","year":"1984"},{"key":"S0960129524000252_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(99)80018-4"},{"key":"S0960129524000252_ref26","unstructured":"Odifreddi, P. G. (1989). Classical recursion theory. Studies in Logic and the Foundations of Mathematics, vol. 125, North\u2013Holland."},{"key":"S0960129524000252_ref23","volume-title":"Mathematical Foundations of Computer Science","volume":"176","author":"Longo","year":"1984"},{"key":"S0960129524000252_ref21","first-page":"472","article-title":"Extending partial combinatory algebras","volume":"16","author":"Klop","year":"1982","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"S0960129524000252_ref34","unstructured":"Longley, J. (1994). Realizability Toposes and Language Semantics, PhD thesis, University of Edinburgh."},{"key":"S0960129524000252_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0062852"},{"key":"S0960129524000252_ref27","volume-title":"Classical Recursion Theory","volume":"143","author":"Odifreddi","year":"1999"},{"key":"S0960129524000252_ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0755-0_14"},{"key":"S0960129524000252_ref7","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1996.561461"},{"key":"S0960129524000252_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0960129524000252_ref18","first-page":"1","volume-title":"Computability in Europe 2018","author":"Khoussainov","year":"2018"},{"key":"S0960129524000252_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2021.50"},{"key":"S0960129524000252_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61254-8_19"},{"key":"S0960129524000252_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3"},{"key":"S0960129524000252_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47992-6"},{"volume-title":"Computability and Logic","year":"1974","author":"Boolos","key":"S0960129524000252_ref9"},{"key":"S0960129524000252_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9452-5"},{"key":"S0960129524000252_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-64309-5_21"},{"key":"S0960129524000252_ref37","volume-title":"Realizability: An Introduction to Its Categorical Side","volume":"152","author":"van Oosten","year":"2008"},{"key":"S0960129524000252_ref35","volume-title":"Constructivism in Mathematics","volume":"123","author":"Troelstra","year":"1988"},{"key":"S0960129524000252_ref16","doi-asserted-by":"publisher","DOI":"10.1215\/00294527-2023-0002"},{"key":"S0960129524000252_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70730-4"},{"key":"S0960129524000252_ref4","unstructured":"Bethke, I. (1988). Notes on Partial Combinatory Algebras. Phd thesis, Universiteit van Amsterdam."},{"volume-title":"The Foundations of Intuitionistic Mathematics","year":"1965","author":"Kleene","key":"S0960129524000252_ref20"},{"key":"S0960129524000252_ref5","doi-asserted-by":"publisher","DOI":"10.2307\/2274368"},{"key":"S0960129524000252_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2008.04.005"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129524000252","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,6]],"date-time":"2024-11-06T08:52:55Z","timestamp":1730883175000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129524000252\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["S0960129524000252"],"URL":"https:\/\/doi.org\/10.1017\/s0960129524000252","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2024,6]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}