In this model we are concerned with functions on the natural numbers, Nat = {0, 1, 2, 3, … }. The recursive functions on Nat are developed entirely in terms of function concepts without any explicit computationalmodel.
Definition 8.2.1: an initial function is one of the following:
(1) the constant function, zero, defined for all x_Nat by zero(x) = 0,
(2) the successor function, succ, defined for all x_Nat by succ(x) = x+1, and
(3) for each nŤ1 and 1ŠkŠn, a projection function taking n arguments, _n, defined for all xi_Nat (1ŠiŠn) by _n(x1, x2, … , xn) = xk.
k
k
Previous slide | Next slide | Back to first slide | View graphic version |