Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

Chapter 2. General Recursive Functions > 2.1 Primitive Recursive Functions - Pg. 29

2 General Recursive Functions In the preceding chapter, we saw an overview of several possible formalizations of the concept of effective calculability. In this chapter, we focus on one of those: primitive recursiveness and search, which give us the class of general recursive partial functions. In particular, we develop tools for showing that certain functions are in this class. These tools will be used in Chapter 3, where we study computability by register- machine programs. 2.1 Primitive Recursive Functions The primitive recursive functions have been defined in the preceding chapter as the functions on N that can be built up from zero functions f (x 1 , . . . , x k ) = 0, the successor function S(x) x 1,