{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T20:57:11Z","timestamp":1757624231432,"version":"3.44.0"},"reference-count":45,"publisher":"SAGE Publications","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["COM"],"published-print":{"date-parts":[[2023,12,21]]},"abstract":"<jats:p>Partiality is a natural phenomenon in computability that we cannot get around. So, the question is whether we can give the areas where partiality occurs, that is, where non-termination happens, more structure. In this paper we consider function classes which besides the total functions only contain finite functions whose domain of definition is an initial segment of the natural numbers. Such functions appear naturally in computation. We show that a rich computability theory can be developed for these functions classes which embraces the central results of classical computability theory, in which all partial (computable) functions are considered. To do so, the concept of a G\u00f6del number is generalised, resulting in a broader class of numberings. The central algorithmic idea in this approach is to search in enumerated lists. In this way, function computability is reduced to set listability. Besides the development of a computability theory for the functions classes, the new numberings \u2013 called quasi-G\u00f6del numberings \u2013 are studied from a numbering-theoretic perspective: they are complete, and each of the function classes numbered in this way is a retract of the G\u00f6del numbered set of all partial computable functions. Moreover, the Rogers semi-lattice of all computable numberings of the considered function classes is studied and results as in the case of the computable numberings of the partial computable functions are obtained. The function classes are shown to be effectively given algebraic domains in the sense of Scott\u2013Ershov. The quasi-G\u00f6del numberings are exactly the admissible numberings of the computable elements of the domain. Moreover, the domain can be computably mapped onto every other effectively given one so that every admissible numbering of the computable domain elements is generated by a quasi-G\u00f6del numbering via this mapping.<\/jats:p>","DOI":"10.3233\/com-230463","type":"journal-article","created":{"date-parts":[[2023,12,19]],"date-time":"2023-12-19T12:16:37Z","timestamp":1702988197000},"page":"371-426","source":"Crossref","is-referenced-by-count":0,"title":["How much partiality is needed for a theory of computability?"],"prefix":"10.1177","volume":"12","author":[{"given":"Dieter","family":"Spreen","sequence":"first","affiliation":[{"name":"ATHENA Visiting Researcher (AVR) Programme\/Le Studium, France"},{"name":"Laboratoire d\u2019Informatique Fondamentale d\u2019Orl\u00e9ans (LIFO), (University of Orl\u00e9ans, INSA Centre Val de Loire), France"},{"name":"Department of Mathematics, University of Siegen, Germany"}]}],"member":"179","reference":[{"unstructured":"O. Aberth, Computable Analysis, McGraw-Hill, New York, 1980.","key":"10.3233\/COM-230463_ref1"},{"doi-asserted-by":"crossref","unstructured":"S. Abramsky and A. Jung, Domain theory, in: Semantic Structures, S. Abramsky et al., eds, Handbook of Logic in Computer Science, Vol. 3, Clarendon Press, Oxford, 1994, pp. 1\u2013168.","key":"10.3233\/COM-230463_ref2","DOI":"10.1093\/oso\/9780198537625.003.0001"},{"doi-asserted-by":"crossref","unstructured":"R.M. Amadio and P.-L. Curien, Domains and Lambda-Calculi, Cambridge University Press, Cambridge, 1998.","key":"10.3233\/COM-230463_ref3","DOI":"10.1017\/CBO9780511983504"},{"unstructured":"M. Davis, Computability and Unsolvability, Mc-Graw-Hill, New York, 1958.","key":"10.3233\/COM-230463_ref4"},{"key":"10.3233\/COM-230463_ref6","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF02219096","article-title":"Computable functionals of finite types","volume":"11","author":"Ershov","year":"1972","journal-title":"Algebra i Logika"},{"key":"10.3233\/COM-230463_ref7","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/malq.19730191901","article-title":"Theorie der numerierungen I","volume":"19","author":"Ershov","year":"1973","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"key":"10.3233\/COM-230463_ref8","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1002\/malq.19750210164","article-title":"Theorie der numerierungen II","volume":"21","author":"Ershov","year":"1975","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"doi-asserted-by":"crossref","unstructured":"G. Gierz, K.H. Hoffmann, K. Keimel, J.D. Lawson, M.W. Mislove and D.S. Scott, Continuous Lattices and Domains, Cambridge University Press, Cambridge, 2003.","key":"10.3233\/COM-230463_ref9","DOI":"10.1017\/CBO9780511542725"},{"key":"10.3233\/COM-230463_ref10","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1002\/malq.19740200808","article-title":"Die struktur des halbverbandes der effektiven numerierungen","volume":"20","author":"Goetze","year":"1974","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"key":"10.3233\/COM-230463_ref11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1002\/malq.19760220125","article-title":"The structure of the lattice of recursive sets","volume":"22","author":"Goetze","year":"1976","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"key":"10.3233\/COM-230463_ref12","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0304-3975(83)90036-1","article-title":"Computation of recursive functionals using minimal initial segments","volume":"23","author":"Gordon","year":"1983","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"C.A. Gunter and D.S. Scott, Semantic domains, in: Handbook of Theoretical Computer Science, Vol. B, Formal Models and Semantics, J. van Leeuwen, ed., Elsevier, Amsterdam, 1990, pp. 633\u2013674.","key":"10.3233\/COM-230463_ref13","DOI":"10.1016\/B978-0-444-88074-1.50017-2"},{"key":"10.3233\/COM-230463_ref14","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1002\/malq.19710170135","article-title":"Zur Pr\u00e4zisierung des Begriffs berechenbare reelle Funktion","volume":"17","author":"Hauck","year":"1971","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"key":"10.3233\/COM-230463_ref15","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1002\/malq.19730190804","article-title":"Berechenbare reelle Funktionen","volume":"19","author":"Hauck","year":"1973","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"key":"10.3233\/COM-230463_ref16","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1002\/malq.19760220136","article-title":"Berechenbare reelle Funktionenfolgen","volume":"22","author":"Hauck","year":"1976","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"key":"10.3233\/COM-230463_ref17","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1002\/malq.19780241912","article-title":"Konstruktive Darstellungen reeller Zahlen und Funktionen","volume":"24","author":"Hauck","year":"1978","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"doi-asserted-by":"publisher","key":"10.3233\/COM-230463_ref18","DOI":"10.1007\/BFb0099488"},{"key":"10.3233\/COM-230463_ref19","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0003-4843(79)90006-8","article-title":"Filter spaces and continuous functionals","volume":"16","author":"Hyland","year":"1979","journal-title":"Annals of Mathematical Logic"},{"doi-asserted-by":"publisher","key":"10.3233\/COM-230463_ref20","DOI":"10.1007\/BFb0036923"},{"unstructured":"W.H. Kersjes, Rekursionstheorie auf Teilmengen von P. Diplomarbeit, RWTH, Aachen, 1982.","key":"10.3233\/COM-230463_ref21"},{"key":"10.3233\/COM-230463_ref22","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF02219834","article-title":"On the reducibility of computable numerations","volume":"8","author":"Khutoretski\u012d","year":"1969","journal-title":"Algebra i Logika"},{"key":"10.3233\/COM-230463_ref23","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/BF01565439","article-title":"General recursive functions of natural numbers","volume":"112","author":"Kleene","year":"1936","journal-title":"Mathematische Annalen"},{"unstructured":"S.C. Kleene, Introduction to Metamathematics, Van Nostrand, Princeton, NJ, 1952.","key":"10.3233\/COM-230463_ref24"},{"key":"10.3233\/COM-230463_ref25","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(85)90208-7","article-title":"Theory of representation","volume":"38","author":"Kreitz","year":"1985","journal-title":"Theoretical Computer Science"},{"key":"10.3233\/COM-230463_ref26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/malq.19640100203","article-title":"Standard classes of recursively enumerable sets","volume":"10","author":"Lachlan","year":"1964","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"unstructured":"A.I. Mal\u2019cev, Algorithms and Recursive Functions, Wolters-Noordhoff, Groningen, 1970.","key":"10.3233\/COM-230463_ref27"},{"unstructured":"A.I. Mal\u2019cev, The Metamathematics of Algebraic Structures, B.F. Wells III., ed., Collected Papers: 1936\u20131967, North-Holland, Amsterdam, 1971.","key":"10.3233\/COM-230463_ref28"},{"doi-asserted-by":"publisher","key":"10.3233\/COM-230463_ref29","DOI":"10.1007\/3-540-13331-3_33"},{"key":"10.3233\/COM-230463_ref31","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1002\/malq.19550010407","article-title":"Effective operations on partial recursive functions","volume":"1","author":"Myhill","year":"1955","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"unstructured":"P.G. Odifreddi, Classical Recursion Theory, Elsevier, Amsterdam, 1992.","key":"10.3233\/COM-230463_ref32"},{"key":"10.3233\/COM-230463_ref33","first-page":"252","article-title":"G\u00f6del numberings versus Friedberg numberings","volume":"15","author":"Pour-El","year":"1964","journal-title":"Proceedings of the American Mathematical Society"},{"doi-asserted-by":"crossref","unstructured":"M.B. Pour-El and J.I. Richards, Computability in Analysis and Physics, Springer, Berlin, 1989.","key":"10.3233\/COM-230463_ref34","DOI":"10.1007\/978-3-662-21717-7"},{"key":"10.3233\/COM-230463_ref35","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1090\/S0002-9947-1953-0053041-6","article-title":"Classes of recursively enumerable sets and their decision problems","volume":"74","author":"Rice","year":"1953","journal-title":"Transactions of the American Mathematical Society"},{"key":"10.3233\/COM-230463_ref36","doi-asserted-by":"publisher","first-page":"331","DOI":"10.2307\/2964292","article-title":"G\u00f6del numberings of partial recursive functions","volume":"23","author":"Rogers","year":"1958","journal-title":"Journal of Symbolic Logic"},{"unstructured":"H. Rogers Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967.","key":"10.3233\/COM-230463_ref37"},{"unstructured":"D. Scott, Outline of a Mathematical Theory of Computation. Technical Monograph PRG-2, Oxford University Computing Laboratory, 1970.","key":"10.3233\/COM-230463_ref38"},{"unstructured":"D. Scott, Lectures on a Mathematical Theory of Computation. Technical Monograph PRG-19, Oxford University Computing Laboratory, 1981.","key":"10.3233\/COM-230463_ref39"},{"doi-asserted-by":"publisher","key":"10.3233\/COM-230463_ref40","DOI":"10.1007\/BFb0012801"},{"issue":"1","key":"10.3233\/COM-230463_ref42","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/0890-5401(90)90032-D","article-title":"Computable one-to-one enumerations of effective domains","volume":"84","author":"Spreen","year":"1990","journal-title":"Information and Computation"},{"doi-asserted-by":"crossref","unstructured":"V. Stoltenberg-Hansen, I. Lindstr\u00f6m and E.R. Griffor, Mathematical Theory of Domains, Cambridge University Press, Cambridge, 1994.","key":"10.3233\/COM-230463_ref43","DOI":"10.1017\/CBO9781139166386"},{"issue":"1","key":"10.3233\/COM-230463_ref44","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","article-title":"On computable numbers, with an application to the Entscheidungsproblem","volume":"s2-42","author":"Turing","year":"1936","journal-title":"Proceedings of the London Mathematical Society"},{"key":"10.3233\/COM-230463_ref45","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1112\/plms\/s2-43.6.544","article-title":"A correction","volume":"s2-43","author":"Turing","year":"1937","journal-title":"Proceedings of the London Mathematical Society"},{"doi-asserted-by":"crossref","unstructured":"K. Weihrauch, Computability, Springer, Berlin, 1987.","key":"10.3233\/COM-230463_ref46","DOI":"10.1007\/978-3-642-69965-8"},{"doi-asserted-by":"crossref","unstructured":"K. Weihrauch, Computable Analysis, Springer, Berlin, 2000.","key":"10.3233\/COM-230463_ref47","DOI":"10.1007\/978-3-642-56999-9"},{"key":"10.3233\/COM-230463_ref49","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(83)90083-X","article-title":"Admissible representations of effective cpo-s","volume":"26","author":"Weihrauch","year":"1983","journal-title":"Theoretical Computer Science"}],"container-title":["Computability"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/COM-230463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T12:22:17Z","timestamp":1757420537000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-230463"}},"subtitle":[],"editor":[{"given":"Nikolay","family":"Bazhenov","sequence":"additional","affiliation":[]},{"given":"Takayuki","family":"Kihara","sequence":"additional","affiliation":[]},{"given":"Svetlana","family":"Selivanova","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2023,12,21]]},"references-count":45,"journal-issue":{"issue":"4"},"URL":"https:\/\/doi.org\/10.3233\/com-230463","relation":{},"ISSN":["2211-3576","2211-3568"],"issn-type":[{"type":"electronic","value":"2211-3576"},{"type":"print","value":"2211-3568"}],"subject":[],"published":{"date-parts":[[2023,12,21]]}}}