Problem Solving in Automata, Languages, and Complexity

214 TURING MACHINES

*10.

functions. Show that the following function f is primitive recursive:

f(o7 4 = s(n),

f (m + 1, n> = f (m, h(m, n)).

[Hi&: Introduce a third parameter and then apply the operation of

primitive recursion on the third parameter.]

Assume that gl, g2 and h are all primitive recursive.

following function f is primitive recursive:

Show that the

f(0, n) = s&--J>,

f(m + l,O> = gz(m>,

f(m + 1, n + 1) = h(m, n, f(m + 1, n), f(m, 7-4 + 1)).

[Hint: Use the pairing

input .]

function to encode the two inputs into a single

• 
  
  
  
  11. Assume that gl, g2 and h are all primitive recursive. Show that the
  
  
  
  

following function f is primitive recursive:

f(0-g = s&-g,

f (m + LO) = ga(m),

f(m+ Ln+ 1) = h(m,n,f(m,n),f(n,m),f(m,m),f(n,n)).

[Hint: Use the pairing function f2 defined in Exercise l(b) of this section

to encode the two inputs into a single input.]

12. Assume that gl , g2, hl and h2 are all primitive recursive. Let fi and f2

be functions defined by the following formulas:

f1(m,O) = s1(m>,

f2@-b 0) = gz@-q,

f1(m,n+ q= hl(m,n,fl(m,n),fi(m,n)),

f2(m, 72 + 1) = hz(7v-b fl(n-v>, f2(m, n>>*

Show that both fi and f2 are primitive recursive:

4.8 Partial Recursive Functions

All primitive recursive functions are total functions; that is, they are defined on

every possible input. In this section, we extend the class of primitive recursive

functions to the class of partial recursive functions by adding a new operation,

called unbounded minimization, which may produce nontotal functions from

total functions. Recall that f(n) T d enotes the fact that f is undefined at

input 72.