Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-23T22:34:56.122Z Has data issue: false hasContentIssue false
  • English
  • Français

Reducibilities in two models for combinatory logic

Published online by Cambridge University Press:  12 March 2014

Luis E. Sanchis
Luis E. Sanchis*
Affiliation:
School of Computer and Information Science, Syracuse University, Syracuse NY 13210
Get access Rights & Permissions [Opens in a new window]

Extract

This paper proposes a generalization of several reducibilities in the sense of recursive function theory. For this purpose two structures are introduced as models of combinatory logic and reducibilities are defined in a rather natural way by means of the application operation in each model. The first model we consider is called the graph model and was introduced by Dana Scott in [11]. Reducibilities in this model are generalizations of enumeration and Turing reducibilities. The second model is called the hypergraph model and induces reducibilities which are generalizations of hyperenumeration and hyperarithmetical reducibilities.

The possibility of formulating reducibilities in this way is not new. For the graph model it is implicit in [7] and for the hypergraph model in [9]. On the other hand it is possible to look at the present method as a variant of the well-known technique of relativization in recursive function theory. We think that this does not exhaust the power of the method, which is conceptually elegant and provides a natural frame for the results of this paper.

In the first part of the paper we discuss the definition and general properties of the models. Then we introduce the reducibilities in the graph model and prove several theorems which are generalizations of properties already Known for enmeration and Turing reducibilities. Next we define reducibilities in the hypergraph model and try to extend the preceding results. For this purpose we prove two theorems showing significant relations between the operators in both models. In fact we prove that each operator in the hypergraph model can be simulated on a comeager set by an operator of the graph model.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 44 , Issue 2 , June 1979 , pp. 221 - 234
Copyright
Copyright © Association for Symbolic Logic 1979

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]Case, John, Enumeration reducibility and partial degrees, Annals of Mathematical Logic, vol. 2(1971), pp. 419–440.CrossRefGoogle Scholar
[2]Curry, Haskell B. and Feys, Robert, Combinatory logic, vol. I, North-Holland, Amsterdam, 1958.Google Scholar
[3]Davis, Martin, Computability and unsolrability, McGraw-Hill, New York, 1958.Google Scholar
[4]Friedman, Harvey, Axiomatic recursive function theory, Logic Colloquium '69 (Gandy, R. O. and Yates, C. E. M., Editors), North-Holland, Amsterdam, 1971.Google Scholar
[5]Kelley, John L., General topology, American Book Company, New York, 1955.Google Scholar
[6]Myhill, John, Category methods in recursion theory, Pacific Journal of Mathematics, vol. 11 (1961), pp. 1479–1486.CrossRefGoogle Scholar
[7]Rogers, Hartley Jr, Theory of recursive functions and effective computability, Mc-Graw-Hill, New York, 1967.Google Scholar
[8]Sanchis, Luis E., Data types as lattices: retractions, closures and projections, R.A.I.R.O. Informatique théorique, Theoretical Computer Science, vol. 11 (1977), pp. 329–344.CrossRefGoogle Scholar
[9]Sanchis, Luis E., Hyperenumeration redubility, Notre Dame Journal of Formal Logic, vol. 19 (1978), pp. 405–415.CrossRefGoogle Scholar
[10]Sasso, Leonard P. Jr., A survey of partial degrees, this Journal, vol. 40 (1975), pp. 130–140.Google Scholar
[11]Scott, Dana, Lambda calculus and recursion theory, Proceedings of the Third Scandinavian Logic Symposium, North-Holland, Amsterdam, 1973.Google Scholar
[12]Shoenfield, Joseph R., An uncountable set of incomparable degrees, Proceedings of the American Mathematical Society, vol. 11 (1960), pp. 61–62.CrossRefGoogle Scholar
[13]Thomason, Steven K., The forcing method and the upper semilattice of hyperdegrees, Transactions of the American Mathematical Society, vol. 129 (1967), pp. 38–57.CrossRefGoogle Scholar