+1 credit
| Version | Summary | Created by | Modification | Content Size | Created at | Operation |
|---|---|---|---|---|---|---|
| 1 | Sirius Huang | -- | 1706 | 2022-12-01 01:35:20 |
Video Upload Options
In mathematical logic and computer science, the general recursive functions (often shortened to recursive functions) or μ-recursive functions are a class of partial functions from natural numbers to natural numbers that are "computable" in an intuitive sense. In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines(this is one of the theorems that supports the Church–Turing thesis). The μ-recursive functions are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every μ-recursive function is a primitive recursive function—the most famous example is the Ackermann function. Other equivalent classes of functions are the λ-recursive functions and the functions that can be computed by Markov algorithms. The subset of all total recursive functions with values in {0,1} is known in computational complexity theory as the complexity class R.
References
- Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, 1972
- Boolos, G. S., Burgess, J. P., Jeffrey, R. C., Computability and Logic, Cambridge Univerity Press, 2007
- Jones, N. D., Computability and Complexity: From a Programming Perspective, The MIT Press, Cambridge, Massachusetts, London, England, 1997
- Kfoury, A. J., R. N. Moll, and M. A. Arbib, A Programming Approach to Computability, 2nd ed., Springer-Verlag, Berlin, Heidelberg, NewYork, 1982
- Stephen Cole Kleene (Jan 1943). "Recursive predicates and quantifiers". Transactions of the American Mathematical Society 53 (1): 41–73. doi:10.1090/S0002-9947-1943-0007371-8. https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf.
