Good introductory books on primitive recursive functions

Solution 1:

Check out Haskell's site on Recursive function theory. That would be a good start, and you'll likely find more references as you look through the table of contents.

See also Primitive Recursive Functions 1, and Primitive Recursive Functions 2. Again, you'll find additional links to explore for clarification, as well as some suggested resources to get you on your way.

You might want to check out Boolos, Burgess, and Jeffrey's Computatibility and Logic. There's a chapter on recursive functions, starting with primitive recursive functions, and a subsequent section on recursive relations. (You can preview the text and its table of contents at the link above to see if it might meet your needs.)

You'll also find a nice pdf/handout (actually, a book chapter) from UPenn: Primitive Recursion

Solution 2:

Nigel Cutland's Computability: An Introduction to Recursive Function Theory is a nice gentle way into the area, although personally I found it a little slow going. Nonetheless if you want your hand held and a lot of time spent on the basics, Cutland is very good.

Once you're ready for something more rigorous and in-depth, I have to recommend Hartley Rogers's classic, Theory of Recursive Functions and Effective Computability. When you first start to read it it will seem impossibly dense, all cryptic notation and difficult ideas. But it's actually extremely well written and very clear despite its age (it dates to 1967).

As with many such books you should skip the introduction which sets out prerequisites and explains the notation: it will just slow you down and demotivate you. Instead, dive straight into the first chapter on recursive functions, which nicely motivates the problem and makes clear the key distinction between a function and a method for computing a function.

A copy should be available in any good university library, and secondhand copies can be had for very little money online. Cutland's book is also commonly assigned and so should also be available in your university library.