Chapter 11: Computability ~ 329
concat(ax], X2) = cons a (concat(xb X2))
concat(bx] , X2) = cons b (concat(x], X2))
SO concat is defined by recursion using id, cons a and cons b.
Therefore, concat is primitive recursive.
(d) The transpose function can be defined by trans(x) = x
T . Then
trans(A) = A
trans(ax) = concat(trans(x), a(x))
trans(bx) = concat(trans(x), b(x))
Therefore, trans(x) is primitive recursive.
(e) The head function head(x) satisfies
head(A) = A
head(ax) = a(x)
head(bx) = b(x)
Therefore, head(x) is primitive recursive.
(f) The tail function tail(x) satisfies
tail(A) = A
tail(ax) = id(x)
tail(bx) = id(x)
Therefore, tailex-) is pnm]t]ve recursive.
(g) The conditional function can be defined by
cond(x], X2, X3) = "if x] "* A then X:; else X3"
Then,
cond(A, Xb x3) = id(x3)
cond(ax], X:;, X3) = id(x:;)
cond(bx], X2, X3) = id(x:;)
Therefore, id(x], x2. :\"3) is primitive recursive.
11.3 RECURSIVE FUNCTIONS
By introducing one more operation on functions, we define the class of
recursive functions, which includes the class of primitive recursive functions.
Def"mition 11.8 Let g(x], X2' ..., X/1' y) be a total function over N. g is a
regular function if there exists some natural number Yo such that g(x], X2, .. ",
XII' Yo) = 0 for all values X], X2, ..., X/1 in N.