200 TURING MACHINES
halts with output w. (In particular, if the current instruction label is Li,
with i greater than the number 12 of instructions in P, then the machine
halts.)
For any LMA A& we let L(M) = { 1x3 E C* 1 A4 halts on z}, We say
A4 computes a partial function f : C + I’, if A4 halts on each input
g E Domain(f) with the final sentential form w = f(z), and A4 does
not halt on any II: 4 Domain(f).
( > a
* Cb)
* (4
* Cd)
Design an LMA k! that computes the function f(z) = xR for
x E {a,b}*.
Show that every Turing-computable function f is computable by
an LMA.
Show that for any LMA M, L(M) is Turing-acceptable.
Show that every partial function f computed by an LMA A4 is
Turing-computable.
4.6 Primitive Recursive Functions
In this section, we consider only integer functions f : N” -+ N, for k > - 1. We
will build a class of integer functions from three types of initial functions and
two operations on functions.
lnitiul Fzanctions. The following functions are called initial functions:
1. (Zero function) c(n) = 0, for n E N.
2. (Successor function) g(n) = n + 1, for n E N.
3. (Projection functions) nf (ni, l l. , nk) = ni .l
Composition: Let m, k be two positive integers. Given functions g : N” +
N and /zi : N’ + N for i = 1,2, l. l , m., define f : N’ + N by
Function f is called the composition of functions g and hl,... , h,. We write
YO(hl,*-, hm) to denote the function f.
Primitive Recursion: Let k > 0. Given g : Nk + N and h : Nk+2 -+ N,
(when k = 0, g is just a constant), define f : N”+l -+ N by
f(~l,**‘,nk,O)=g(~l,“‘,nk),
f(W) l ’ l ‘) nk,m+l) = h(nl,-•,nk,m,.f(nl,-•,nk,m)), m > - 0.‘A remark ab o u t notation: when we write an integer i as a subscript in the function
name, such as $, it means that i is a fixed integer. For instance, the fact that 7r” are
computable by Turing machines for any fixed k and any fixed i, 1 2 i 5 k, does not imply
directly that the function f ‘(rq,... ,nk,i) = $ (nl,... , nk) is computable by a Turing
machine. See also Exercise 2 of this section.