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

Computing with Functionals—Computability Theory or Computer Science?

Published online by Cambridge University Press:  15 January 2014

Dag Normann
Dag Normann*
Affiliation:
Department of Mathematics, The University of Oslo, P.O. Box 1053, Blindern N-0316 Oslo, Norway. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We review some of the history of the computability theory of functionals of higher types, and we will demonstrate how contributions from logic and theoretical computer science have shaped this still active subject.

Type
Articles
Information
Bulletin of Symbolic Logic , Volume 12 , Issue 1 , March 2006 , pp. 43 - 59
Copyright
Copyright © Association for Symbolic Logic 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Abramsky, S., Jagadeesan, R., and Malacaria, P., Full abstraction for PCF, (extended abstract), Theoretical aspects of computer software (Hagiya, M. and Mitchell, J. C., editors), Springer, 1994, pp. 1–15.Google Scholar
[2] Barwise, K. J., Admissible sets and structures, Springer, 1975.Google Scholar
[3] Berger, U., Totale Objekte und Mengen in der Bereichstheorie, Thesis, München, 1990, in German.Google Scholar
[4] Church, A., An unsolvable problem in elementary number theory, American Journal of Mathematics, vol. 58 (1936), pp. 345–363.Google Scholar
[5] Di Gianantonio, P., A functional approach to computability on real numbers, Thesis, Università di Pisa–Genova–Udine, 1993.Google Scholar
[6] Di Gianantonio, P., Real number computability and domain theory, Information and Computation, vol. 127 (1996), pp. 11–25.Google Scholar
[7] Di Gianantonio, P., An abstract data type for real numbers, Theoretical Computer Science, vol. 221 (1999), pp. 295–326.Google Scholar
[8] Ershov, Yu. L., Computable functionals of finite type, Algebra and Logic, vol. 11 (1972), pp. 203–277.Google Scholar
[9] Ershov, Yu. L., The theory of numerations, vol. 2, Novosibirsk, 1973, in Russian.Google Scholar
[10] Ershov, Yu. L., Maximal and everywhere defined functionals, Algebra and Logic, vol. 13 (1974), pp. 210–225.Google Scholar
[11] Hyland, J.M.E., Recursion on the countable functionals, Dissertation, Oxford, 1975.Google Scholar
[12] Hyland, J.M.E. and Ong, C.-H.L., On full abstraction for PCF: I. Models, observables and the full abstraction problem, II. Dialogue games and innocent strategies, III. A fully abstract and universal game model, Information and Computation, vol. 163 (2000), pp. 285–408.Google Scholar
[13] Kleene, S. C., Recursive functionals and quantifiers of finite types I, Transactions of the American Mathematical Society, vol. 91 (1959), pp. 1–52.Google Scholar
[14] Kleene, S. C., Countable functionals, Constructivity in mathematics (Heyting, A., editor), North-Holland, 1959, pp. 81–100.Google Scholar
[15] Kleene, S. C.,Recursive functionals and quantifiers of finite types II, Transactions of the American Mathematical Society, vol. 108 (1963), pp. 106–142.Google Scholar
[16] Kleene, S. C.,Recursive functionals and quantifiers of finite types revisited I, Generalized recursion theory II (Fenstad, J. E., Gandy, R. O., and Sacks, G. E., editors), North-Holland, 1978, pp. 185–222.Google Scholar
[17] Kleene, S. C.,Recursive functionals and quantifiers of finite types revisited II, The Kleene symposium (Barwise, J., Keisler, H. J., and Kunen, K., editors), North-Holland, 1980, pp. 1–29.Google Scholar
[18] Kleene, S. C.,Recursive functionals and quantifiers of finite types revisited III, Patras logic symposion (Metakides, G., editor), North-Holland, 1982, pp. 1–40.Google Scholar
[19] Kleene, S. C.,Unimonotone functions of finite types (Recursive functionals and quantifiers of finite types revisited IV), American Mathematical Society proceedings of symposia in pure mathematics (Nerode, A. and Shore, R. A., editors), Recursion theory, vol. 42, 1985, pp. 119–138.Google Scholar
[20] Kleene, S. C.,Recursive functionals and quantifiers of finite types revisited V, Transactions of the American Mathecal Society, vol. 325 (1991), pp. 593–630.Google Scholar
[21] Kreisel, G., Interpretation of analysis by means of functionals of finite type, Constructivity in mathematics (Heyting, A., editor), North-Holland, 1959, pp. 101–128.Google Scholar
[22] Kuratowski, C., Topologie, vol. 1, Warsawa, 1952.Google Scholar
[23] Loader, R., Unary PCF is decidable, Theoretical Computer Science, vol. 206 (1998), no. 1–2, pp. 317–329.Google Scholar
[24] Loader, R., Finitary PCF is not decidable, Theoretical Computer Science, vol. 266 (2001), no. 1–2, pp. 341–364.Google Scholar
[25] Longley, J. R., The sequentially realizable functionals, Annals of Pure and Applied Logic, vol. 117, no. 1, pp. 1–93.Google Scholar
[26] Longley, J. R., Notions of computability at higher types I, Logic colloquium 2000 (Cori, R. et al., editors), Lecture Notes in Logic, vol. 19, ASL and AK Peters, 2005, pp. 32–142.Google Scholar
[27] Longley, J. R., On the ubiquity of certain total type structures, Proceedings of workshop in domains VI (Birmingham), Electronic Notes in Theoretical Computer Science, vol. 74, Elsevier, 2003, to appear.Google Scholar
[28] Milner, R., Fully abstract models for typed λ-calculi, Theoretical Computer Science, vol. 4 (1977), pp. 1–22.Google Scholar
[29] Milner, R. and Strachey, C., A theory of programming language semantics, Chapman and Hall, London, 1976.Google Scholar
[30] Moldestad, J., Computations in higher types, Lecture Notes in Mathematics, vol. 574, Springer, 1977.Google Scholar
[31] Moschovakis, Y. N., Hyperanalytic predicates, Transactions of the American Mathematical Society, vol. 129 (1997), pp. 249–282.Google Scholar
[32] Normann, D., Set recursion, Generalized recursion theory II (Fenstad, J. E., Gandy, R. O., and Sacks, G. E., editors), North Holland, 1978, pp. 303–320.Google Scholar
[33] Normann, D., The continuous functionals; computations, recursions and degrees, Annals of Mathematical Logic, vol. 21 (1981), pp. 1–26.Google Scholar
[34] Normann, D., Computability over the partial continuous functionals, The Journal of Symbolic Logic, vol. 65 (2000), pp. 1133–1142.Google Scholar
[35] Normann, D., On sequential functionals of type 3, Mathematical structures in Computer Science, to appear.Google Scholar
[36] Platek, R. A., Foundations of recursion theory, Thesis, Stanford University, 1966.Google Scholar
[37] Plotkin, G., LCF considered as a programming language, Theoretical Computer Science, vol. 5 (1977), pp. 223–255.Google Scholar
[38] Plotkin, G., Full abstraction, totality and PCF, Mathematical Structures in Computer Science, vol. 11 (1999), pp. 1–20.Google Scholar
[39] Sacks, G. E., Higher recursion theory, Springer, 1990.Google Scholar
[40] Scott, D., A type-theoretical alternative to ISWIM, CUCH, OWHY, unpublished notes, 1969, Oxford.Google Scholar
[41] Scott, D., A type-theoretical alternative to ISWIM, CUCH, OWHY, Theoretical Computer Science, vol. 121 (1993), pp. 411–440.Google Scholar
[42] Simpson, A., Lazy functional algorithms for exact real functionals, Mathematical foundations of computer science, 1998, Lecture Notes in Computer Science, vol. 1450, Springer, 1998, pp. 456–464.Google Scholar
[43] Tait, W.W., Continuity properties of partial recursive functionals of finite type, unpublished notes, 1958.Google Scholar
[44] Tucker, J. V. and Zucker, J. I., Abstract versus concrete models of computation on partial metric algebras, ACM Transactions on Computational Logic, accepted.Google Scholar