Problem Solving in Automata, Languages, and Complexity

(^206) TURING MACHINES

2. What is wrong with the following proof of Example 4.25?

We prove it by induction on n, as in Example 4.28. When n =

0, s(m,n) = n:(n); so, g(m, 0) is primitive recursive. For n > -

0, g(m, n+l) = f(g(m, n)). Since f is primitive recursive and,

by the inductive hypothesis, g(m, n) is primitive recursive, we

get that g( m, n + 1) is also primitive recursive. It follows that

g (m, n) is primitive recursive for all n 2 0 and, hence, g is

primitive recursive.

3.

4.

5.

6.

Assume that R : N’+l + N is a primitive recursive predicate. Show

that the following function f : N”+l -+ N is also primitive recursive:

(maxi)a<,R(nl,. -.. , nk, i)

f(nl,-+k,m) =

1

if (3i)i<,R(nl, -... , nk, i),

0 otherwise.

Assume that f : Nk+’ + N is primitive recursive. Show that the

following functions are also primitive recursive:

(a) g(nl,-,nk,m) = ~~~.f(nl,-+k,+

(b) h(nl,-+k,m) = n~~.f(nl,-vnk,+

Assume that f : N -+ N is primitive recursive and satisfies f (0) = 0

and f(n) < f(n + 1) f or all n > 0. Show that the function h(m) = [the

integer n such that f(n) < - m 2 f (n + l)] is also primitive recursive.

Assume that both f : N + N and g : N + N are primitive recursive.

Show that the following function h : N2 + N is also primitive recursive:

h(n,O) = f(n),

7.

q-J, r7-2 + 1) = !J(h(n, l=pJ))*

Assume that f : N -+ N is primitive recursive. Show that the following

function g : N2 + N is also primitive recursive:

s(n, 0) = f(n),

s(n, n-2 + 1) = s(s(n, m), m)*

47. Pairing Functions and Gijdel Numberings

In this section, we extend the operation of primitive recursion to more general

recursion operations. For instance, we would like to prove that the Fibonacci

function F : N + N, defined by the double recursion below, is primitive

recursive:

F(0) = 0,

F(1) = 1,

F(n + 2) = F(n) + F(n + 1).