4.8 Partial Recursive Functions 221
Figure 4.19: The Turing machine for SUCC.
Theorem 4.45 For any grammar G over C, L(G) is r.e.
Proof. For any string x E C*, II: E L(G) if and only if (3k)derive&x, k). •I
Next, we show that partial recursive functions are Turing-computable.
First, we show that changing of base is Turing-computable. The basic repre-
sentation for nonnegative integers is Ci = {l}, with the string In representing
the integer n.
Lemma 4.46 For any fixed C, let m : CT + C* be the function m( In) =
Lx(n). Then, both - and r<’ are Turing-computable.
Proof. First, we note that the function succ : C + C which maps a string
x to its successor in the lexicographic ordering is Turing-computable. The
machine A&,,, for succ is shown in Figure 4.19.
Next, we design a three-tape TM M that computes the function 5, using
tape 1 as the input tape, tape 2 as the work tape and tape 3 as the output
tape. We only describe the basic structure of the machine and omit the precise
instructions:
(1) iV copies the input to tape 2.
(2) M repeats step 3 until tape 2 has no symbol 1 left.
(3) M removes a symbol 1 from tape 2 and then simulates the machine
Ad succ on tape 3.
It is clear that when tape 2 has no symbol 1 left, tape 3 will have the nth
string of C* under the lexicographic ordering.
For the function $, we can design a TM A4-i that performs just the inverse
of the above machine AL That is, Mi first copies the input II: to tape 2. Then,
it simulates a machine that computes the inverse function of succ on tape 2
and writes a symbol 1 on tape 3, and it repeats this until tape 2 has no symbol
in C left. We leave the details to the reader as an exercise.^0
