Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T18:04:32.338Z Has data issue: false hasContentIssue false
  • English
  • Français

A relativization mechanism in recursion categories

Published online by Cambridge University Press:  12 March 2014

Stefano Stefani
Stefano Stefani*
Affiliation:
Facolta' di Scienze M. F. N., Dorsoduro 2137, 30123 Venezia, Italy, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

The study of recursion categories was introduced in [DH] to carry out an algebraic and intrinsic investigation of structures and phenomena which arise in the classical recursion theory. In this paper a recursion categorical arrangement is proposed for some of the concepts of reduction and relativization which are commonplace in studying classical recursive functions and operators. Indeed, this introduction can be done in a natural way, using categorical concepts already defined, without resorting to special structures. In developing the subject outlined one also has the opportunity of discussing the concept of uniform proof in the context of the recursion categories.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 58 , Issue 4 , December 1993 , pp. 1251 - 1267
Copyright
Copyright © Association for Symbolic Logic 1993

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

[DH]Di Paola, R. A. and Heller, A., Dominical categories: recursion theory without elements, this Journal, vol. 52 (1987), pp. 594–635.Google Scholar
[HE]Heller, A., An existence theorem for recursion categories, this Journal, vol. 55 (1990), pp. 1252–1268.Google Scholar
[MS]Montagna, F. and Sorbi, A., Creativeness and completeness in categories of partial recursive operators, this Journal, vol. 54 (1989), pp. 1023–1041.Google Scholar
[ME]Medvedev, Ju. T., Degrees of difficulty of the mass problems, Doklady Akademii Nauk SSSR, vol. 104 (1955), pp. 501–504.Google Scholar
[RO]Rogers, H. Jr, Theory of recursive function and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[ROS]Rosolini, G., Continuity and effectiveness in topoi, Ph.D. thesis, Oxford University, Oxford, 1986.Google Scholar
[SO]Sorbi, A., Comparing of the Baire space by means of general recursive operators, Fundamenta Mathematicae, vol. 138 (1991), pp. 1–12.CrossRefGoogle Scholar