218 TURING MACHlNES
Based on the notion of lexicographic ordering and the function LX, we can
extend the notion of partial recursive functions to functions on strings over C.
A partial function f : (C’)” + C* is called a primitive recursive (or, a partial
recursive) function, if the function f” : N’ -+ N, defined by
.&,n2,-~,nk) = L,‘(f(LC(n1),...~L~(nk)))is primitive recursive (or, respectively, partial recursive). A set A C - (C*)” is
called a recursive (or, r.e.) set if the set
ii= {(nl,n2,... ,nk) EN k 1 (Lc(1zl),-d&k)) EA}is recursive (or, respectively, r.e.).
In the following, when the alphabet C is understood, we will simply treat
each string x E C” as a representation of the integer LC~ (n), and will write
x to denote both the string x and the integer it represents. For instance, for
C = {a, b, c}, with a + b + c, we may write but + 1 to denote both the string
immediately following the string but in the lexicographic ordering 4 (i.e., the
string bbu) and the integer ~&buc) + 1 (i.e., the integer 24 + 1 = 25). In
addition, we note that for x, y E C*, x 4 y if and only if L-~(X) < L-‘(Y). So,
we will simply use a single symbol < for both the integer ordering < and the
string ordering 4, when there is no confusion.
We first show that some of the basic operations on strings are primitive
recursive.
Example 4.42 Assume that c = (~1, ~2,... , sk} and s1 -( s2 4 l l l + sk.
Show that the following functions are primitive recursive:
(a) h&> = I4 l
(b) COnCUt~(X~,X2,...,Xk) k = X1X2*-Xk,
(c) substrc(x, i, l?) = the substring y of x
length l, if 1 < - i < - 1x1 und 1 < - e < -
(d) subc(x, y) = [x is a substring of y].
(e) heudc(x, y) = [x is a prefix of y].
(f) tuilc(x, y) = [x is a sufix of y].k > - 1.
starting from the ith symbol with- i + 1; and 0, otherwise.
Proof. First, let us repeat that we treat each of the above functions as an
integer function with each x E C* representing an integer LC~ (x). For instance,
in part (a), the function Zengc maps an integer n to the integer ILc(n)l; and
in part (d), the function subc maps two integers n and m to 1 if LX(~) is a
substring of ~&rz), and to 0, otherwise.
(a) It is easy to see that the least string of length n + 1 is w = slsl l l l s1
(with n + 1 symbols sl) and Mel = k” + k”-’ + l - + 1. Thus, for any
m > 0, IL~(~)J = (minn),<,[kn + knml + -0 + 1 > m].