Problem Solving in Automata, Languages, and Complexity

4.8 Partial Recursive Functions 219

(b) This can be proved by induction. For k = 1, concat~ is just the identity
function. For k > 1,

concat~(xl,... , Xk) = ConCat;-l(xl,... , Xk-1) ’ klXkl +x/p

(c) If 1 < - i < - 1x1 and 1 < - l< - Ix]- i + 1, then

sub&x(x, i,l) = ( “iw&J<x[IYl - = l and

(~u)~<~(~v),<,[]u] - - = i - 1 and uyv = xl].

(In the above, [uyv = x] means [concat~(u,y,v) = xl.)

(d) subC(x, Y) = (~U)tL<,(~V)tl<,[UXV - - = Y]*

(e) hea&+, Y) = (3V)v<y[XV - = Y]*

(f) taikc(x, Y) = (3U)u<,[UX - = Y]* cl

We are ready to prove that the notions of Turing-computability and par-

tial recursiveness are equivalent. We first show that the computation by a

grammar, as describe by Theorem 4.19, is partial recursive.

Lemma 4.43 For any grammar G, the predicate

derive&, v, k) = [u % v in exactly k steps]

is primitive recursive.

Proof. First, the predicate ruZe(x, y) = [x + y is a rule of G] is primitive

recursive: Suppose G has rules xl + yl, x2 + ~2,.. ., X~ + ym. Then,

ruZe(x, y) = [x = xl and y = yl] or [x = x2 and y = y2]

or 0.0 or [x=x, andy=y,].

Next, we observe that the predicate [u 3 v] is primitive recursive:

[u 3 VI = (3w1~l~~l<l~l~3~2~l~zl~l~I~3~~l~I<I~I~3~~lvlll~l - -

[rule(x,y) and u = ~1~x1~2 and v = wlyw2].

(Note: ]w] < KU is equivalent to w < k” + km-l + l + k.)

Finally, we observe that -

derive& v, 0) = eq(u, v),

derive&, v, k + 1) = (3w)l,l+,l+~[derive&, w, k) and w 3 v],

where! is the length of the longest string in the left-hand side of any rule in

G. Therefore, deriveG is primitive recursive.^0