Skip to main content
SpringerLink
Log in

Discrete families of recursive functions and index sets

  • Published:
Algebra and Logic Aims and scope

Abstract

A number of discrete families of recursive functions are studied; exact upper bounds of index sets appearing in the construction are obtained.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. A. Badaev, “Computable enumerations of families of general recursive functions,”Algebra Logika,16, No. 2, 129–148 (1977).

    Google Scholar 

  2. Yu. L. Ershov, “Theorie der Numerierungen I,”Z. Math. Log. Grund. Math.,19, No. 4, 289–388 (1973).

    Google Scholar 

  3. Yu. L. Ershov,Theory of Numerations [in Russian], Nauka, Moscow (1977).

    Google Scholar 

  4. R. V. Freivald, E. B. Kinber, and R. Wiehagen, “Inductive inference and computable one-one numberings,”Z. Math. Log. Grund. Math.,28, No. 5, 463–479 (1982).

    Google Scholar 

  5. S. S. Goncharov, “Autostability of models and Abelian groups,”Algebra Logika,19, No. 1, 23–44 (1980).

    Google Scholar 

  6. W. A. Howard and M. B. Pour-El, “A structural criterion for recursive enumeration without repetition,”Z. Math. Log. Grund. Math.,10, No. 2, 105–114 (1964).

    Google Scholar 

  7. A. B. Khutoretskii, “On the cardinality of the upper semilattice of computable enumerations,”Algebra Logika,10, No. 5, 561–569 (1971).

    Google Scholar 

  8. S. Lempp, “Hyperarithmetical index sets in recursion theory,”Trans. Am. Math. Soc.,303, No. 2, 559–583 (1987).

    Google Scholar 

  9. S. S. Marchenkov, “The computable enumerations of families of recursive functions,”Algebra Logika,11, No. 5, 588–607 (1972).

    Google Scholar 

  10. T. G. McLaughlin, “The family of all recursively enumerable classes of finite sets,”Trans. Am. Math. Soc.,155, No. 1, 127–136 (1971).

    Google Scholar 

  11. T. G. McLaughlin, “Complete index sets of recursively enumerable families,”Comp. Math.,24, No. 1, 83–91 (1972).

    Google Scholar 

  12. V. L. Selivanov, “Enumerations of families of general recursive functions,”Algebra Logika,15, No. 2, 205–226 (1976).

    Google Scholar 

  13. V. L. Selivanov, Ph.D. Dissertation [unpublished], University of Kazan (1977).

  14. V. L. Selivanov, “On index sets of classes of numberings,” in:Probability Methods and Cybernetics [in Russian], Vol. 14, Kazan (1978), pp. 90-103.

  15. V. L. Selivanov, “Some remarks about classes of recursively enumerable sets,”Sib. Mat. Zh.,19, No. 1, 153–160 (1978).

    Google Scholar 

  16. R. I. Soare,Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin (1987).

    Google Scholar 

  17. F. I. Validov, “Recursively enumerable sets and discrete families of general recursive functions,”Izv. Vyssh. Uchebn. Zav., Ser. Mat., No.4, 6–11 (1984).

    Google Scholar 

Download references

Authors
  1. M. Kummer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Wehner
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiao-Ding Yi
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Translated fromAlgebra i Logika, Vol. 33, No. 2, pp. 147-165, March-April, 1994.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kummer, M., Wehner, S. & Yi, XD. Discrete families of recursive functions and index sets. Algebr Logic 33, 85–94 (1994). https://doi.org/10.1007/BF00739994

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00739994

Keywords

Search

Navigation