Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-22T11:53:38.231Z Has data issue: false hasContentIssue false
  • English
  • Français

COMPUTABILITY IN PARTIAL COMBINATORY ALGEBRAS

Part of: Computability and recursion theory General logic

Published online by Cambridge University Press:  05 January 2021

SEBASTIAAN A. TERWIJN
SEBASTIAAN A. TERWIJN*
Affiliation:
DEPARTMENT OF MATHEMATICS RADBOUD UNIVERSITY NIJMEGEN P.O. BOX 9010, 6500 GL NIJMEGEN, THE NETHERLANDS E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We prove a number of elementary facts about computability in partial combinatory algebras (pca’s). We disprove a suggestion made by Kreisel about using Friedberg numberings to construct extensional pca’s. We then discuss separability and elements without total extensions. We relate this to Ershov’s notion of precompleteness, and we show that precomplete numberings are not 1–1 in general.

Keywords

partial combinatory algebraundecidabilityextensional models1–1 numberings

MSC classification

Primary: 03D25: Recursively (computably) enumerable sets and degrees
Secondary: 03B40: Combinatory logic and lambda-calculus 03D45: Theory of numerations, effectively presented structures 03D80: Applications of computability and recursion theory
Type
Articles
Information
Bulletin of Symbolic Logic , Volume 26 , Issue 3-4 , December 2020 , pp. 224 - 240
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
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 in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2021. Published by Cambridge University Press

References

REFERENCES

Arslanov, M. M., On some generalizations of the fixed point theorem. Soviet Mathematics (Izvestiya VUZ. Matematika), vol. 25 (1981), no. 5, pp. 1–10 (English translation).Google Scholar
Barendregt, H. P., The Lambda Calculus, second ed., Studies in Logic and the Foundations of Mathematics, vol. 103, North-Holland, Amsterdam, 1984.Google Scholar
Barendregt, H. P., Representing ‘undefined’ in lambda calculus. Journal of Functional Programming, vol. 2 (1992), no. 3, pp. 367–374.CrossRefGoogle Scholar
Barendregt, H. P. and Terwijn, S. A., Fixed point theorems for precomplete numberings. Annals of Pure and Applied Logic, vol. 170 (2019), pp. 1151–1161.CrossRefGoogle Scholar
Barendregt, H. P. and Terwijn, S. A., Partial combinatory algebra and generalized numberings, preprint, 2019, arXiv:1910.07750.Google Scholar
Beeson, M. J., Foundations of Constructive Mathematics, Springer-Verlag, Berlin, 1985.CrossRefGoogle Scholar
Bethke, I. and Klop, J. W., Collapsing partial combinatory algebras, Higher-Order Algebra, Logic, and Term Rewriting (Dowek, G. et al., editors), Lecture Notes in Computer Science, vol. 1074, Springer, Berlin, 1996, pp. 57–73.Google Scholar
Bethke, I., Klop, J. W., and de Vrijer, R., Extending partial combinatory algebras. Mathematical Structures in Computer Science, vol. 9 (1999), pp. 483–505.CrossRefGoogle Scholar
Cockett, J. R. B. and Hofstra, P. J. W., Introduction to Turing categories. Annals of Pure and Applied Logic, vol. 156 (2008), pp. 183–209.CrossRefGoogle Scholar
Curry, H. B., Grundlagen der kombinatorischen Logik. American Journal of Mathematics, vol. 52 (1930), pp. 509–536, 789–834.CrossRefGoogle Scholar
Ershov, Y. L., Theorie der Numerierungen I. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 19 (1973), pp. 289–388.CrossRefGoogle Scholar
Ershov, Y. L., Theorie der Numerierungen II. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 473–584.CrossRefGoogle Scholar
Feferman, S., A language and axioms for explicit mathematics, Algebra and Logic (Crossley, J. N., editor), Springer, Berlin, 1975, pp. 87–139.CrossRefGoogle Scholar
Friedberg, R. M., Three theorems on recursive enumeration. Journal of Symbolic Logic, vol. 23 (1958), pp. 309–316.CrossRefGoogle Scholar
Hyland, M., Some reasons for generalising domain theory. Mathematical Structures in Computer Science, vol. 20 (2010), no. 2, pp. 239–265.CrossRefGoogle Scholar
Kleene, S. C. and Vesley, R. E., The Foundations of Intuitionistic Mathematics, North-Holland, Amsterdam, 1965.Google Scholar
Kreisel, G., Some reasons for generalizing recursion theory, Logic Colloquium ’69 (Gandy, R. O. and Yates, C. E. M., editors), North-Holland, Amsterdam, 1971, pp. 139–198.CrossRefGoogle Scholar
Kummer, M., Recursive enumeration without repetition revisited, Recursion Theory Week (Ambos-Spies, K., Müller, G. H., Sacks, G. E., editors), Lecture Notes in Mathematics, vol. 1432, Springer-Verlag, Berlin, 1990, pp. 255–276.CrossRefGoogle Scholar
Longley, J., Realizability toposes and language semantics, Ph.D. thesis, Edinburgh University, 1995.Google Scholar
Longley, J. and Normann, D., Higher-Order Computability, Springer, Berlin, 2015.CrossRefGoogle Scholar
Odifreddi, P., Classical Recursion Theory, vol. 1, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland, Amsterdam, 1989.Google Scholar
Rogers, H. Jr., Theory of Recursive Functions and Effective Computability, McGraw Hill, New York, 1967.Google Scholar
Sacks, G. E., Higher Recursion Theory, Springer-Verlag, Berlin, 1990.CrossRefGoogle Scholar
Schönfinkel, M., Über die Bausteine der mathematischen Logik. Mathematische Annalen, vol. 92 (1924), pp. 305–316.CrossRefGoogle Scholar
Selivanov, V., Index sets of quotient objects of the Post numeration. Algebra i Logika, vol. 27 (1988), no. 3, pp. 343–358 (English translation 1989).Google Scholar
Soare, R. I., Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
Terwijn, S. A., Generalizations of the recursion theorem. Journal of Symbolic Logic, vol. 83 (2018), no. 4, pp. 1683–1690.CrossRefGoogle Scholar
Troelstra, A. S. and van Dalen, D., Constructivism in Mathematics, vol. II, Studies in Logic and the Foundations of Mathematics, vol. 123, North-Holland, Amsterdam, 1988.Google Scholar
van Oosten, J., A general form of relative recursion. Notre Dame Journal of Formal Logic, vol. 47 (2006), no. 3, pp. 311–318.CrossRefGoogle Scholar
van Oosten, J., Realizability: An Introduction to Its Categorical Side, Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, Amsterdam, 2008.Google Scholar
van Oosten, J. and Voorneveld, N., Extensions of Scott’s graph model and Kleene’s second algebra. Indagationes Mathematicae, vol. 29 (2018), pp. 5–22.CrossRefGoogle Scholar
Yates, C. E. M., Review of [17]. Journal of Symbolic Logic, vol. 40 (1975), pp. 230–232.CrossRefGoogle Scholar