Abstract: The class of partial recursive functions is the mathematical abstraction of the class of partial functions computable by an algorithm. In this chapter we present them in the form of the μ-recursive functions. We then state some basic results, the main motivation being to set the stage for the theory of effective domains. Finally we show that the partial μ-recursive functions can be obtained from some simple initial functions using substitution and the fixed point theorem for computable functional. This illuminates the central role of taking fixed points and supports the claim of Chapter 1 that the function computed by an algorithm or a program is the least fixed point of a computable functional.
Publication Year: 1994
Publication Date: 1994-09-22
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot