Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-23T06:17:43.170Z Has data issue: false hasContentIssue false
  • English
  • Français

Computability over the partial continuous functionals

Published online by Cambridge University Press:  12 March 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 show that to every recursive total continuous functional Φ there is a PCF-definable representative Ψ of Φ in the hierarchy of partial continuous functionals, where PCF is Plotkin's programming language for computable functionals. PCF-definable is equivalent to Kleene's S1–S9-computable over the partial continuous functionals.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 65 , Issue 3 , September 2000 , pp. 1133 - 1142
Copyright
Copyright © Association for Symbolic Logic 2000

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]Bellantoni, S., Comments on two notions of higher type computability, unpublished notes, 1990.Google Scholar
[2]Berger, U., Totale objekte und mengen in der bereichtheorie, Thesis, München, 1990, in german.Google Scholar
[3]Berger, U., Total sets and objects in domain theory, Annals of Pure and Applied Logic, vol. 60 (1993), pp. 91–117.CrossRefGoogle Scholar
[4]Ershov, Yu. L., Computable functionals of finite type, Algebra and Logic, vol. 11 (1972), pp. 203–277.CrossRefGoogle Scholar
[5]Hyland, J. M. E., Filterspaces and continuous functionals, Annals of Mathematical Logic, vol. 16 (1979), pp. 101–143.CrossRefGoogle Scholar
[6]Kleene, S.C., Countable functionals, Constructivity in mathematics (Heyting, A., editor), North-Holland, 1959, pp. 81–100.Google Scholar
[7]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
[8]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
[9]Longo, G. and Moggi, E., The hereditarily partial effective functionals and recursion theory in higher types, This Journal, vol. 49 (1984), pp. 1319–1332.Google Scholar
[10]Moldestad, J., Computation in higher types, Springer Lecture Notes in Mathematics, vol. 574, 1977.CrossRefGoogle Scholar
[11]Normann, D., Nonobtainable continuous functionals, Logic, methodology and philosophy of science VI. Proceedings of the sixth international congress on logic, methodology and philosophy of science (Hannover), 1979, pp. 241–249.Google Scholar
[12]Normann, D., Recursion on the continuous functionals, Springer Lecture Notes in Mathematics, vol. 811, 1980.CrossRefGoogle Scholar
[13]Normann, D., The continuous functionals; computations, recursions and degrees, Annals of Mathematical Logic, vol. 21 (1981), pp. 1–26.CrossRefGoogle Scholar
[14]Normann, D., The continuous functionals, Handbook of computability theory (Griffor, E. R., editor), Elsevier, 1999, pp. 251–275.Google Scholar
[15]Plotkin, G., LCF considered as a programming language, Theoretical Computer Science, vol. 5 (1977), pp. 223–255.CrossRefGoogle Scholar
[16]Plotkin, G., Full abstraction, totality and PCF, Mathematical Structures in Computer Science, vol. 11 (1999), pp. 1–20.Google Scholar
[17]Stoltenberg-Hansen, V., Lindström, I., and Griffor, E. R., Mathematical theory of domains, Cambridge Tracts in Theoretical Computer Science, vol. 22, Cambridge University Press, 1994.CrossRefGoogle Scholar
[18]Tait, W. W., Continuity properties ofpartial recursive functionals offinite type, unpublished notes.Google Scholar