On completing this chapter, you should be able to:

define

*initial functions*that are the buliding blocks of computable functionspresent primitive recursive definitions for commonly used functions

state the definition of a recursive function

compute the values of the Ackerman’s function for various values of its variables

state the definition of a computable function

prove that a given function is computable by constructing a Turing machine, which computes the given function

give the sketch of the proof of the theorem, which asserts that every recursive function is computable

recognize that the class of recursive and computable functions are identical

Start Free Trial

No credit card required