Problem Solving in Automata, Languages, and Complexity

4.8 Partial Recursive Functions 223

Minimization. Assume that g : N’“+l + N is a total predicate and that

f(nl,... , nk) = (minm) g(nl,... ,nk,m).

Also assume that there is a 3-tape TM MS computing g. We design a new

4-tape TM M to compute f. The idea of the machine M is to simulate Mg

with inputs (121,... , nk, ?n) for m = 0, 1,... until it outputs 1.

(1) M copies the inputs (nl,... , nk) to tape 2, and then adds an input 0 to

tape 2.

(2) M repeats step 3 until tape 3 has the value 1. If tape 3 has the value

1, then M erases it and copies the last block of l’s of tape 2 to tape 3

as the output.

(3) M simulates machine MS, using tape 2 as the input tape, tape 3 as the

output tape and tape 4 as the work tape. When Mg halts and has an

output not equal to 1, then M erases the output and adds 1 to the last

input of tape 2. Cl

Corollary 4.48 A partial function f : (C’)” + C* is partial recursive if and

only if it is Turing-computable.

Corollary 4.49 A set A C - (,*)I, is recursive if and only if it is Turing-

decidable.

Corollary 4.50 Let A be a subset of (C’)“, k > - 1. The following are equiv-

alent:

(a) A is Turing-acceptable.

(b) A = L(G) f or some unrestricted grammar G.

(c) A is r.e.

Proof. The direction (a) > (b) is proved in Theorem 4.20, (b) 3 (c) is

Theorem 4.45, and (c) + (a) f o 11 ows immediately from Theorem 4.47. U

Exercises 4.8

3,

Design a multi-tape Turing machine that “adds” two strings over C =

(1 4 2 ‘“’ , X}; that is, on inputs x, y E C*, compute x E C* such that

Lx ( ) x = Lx -l(x) + g(y)*

Complete the proof of the primitive recursion part of Theorem 4.47.

That is, given multi-tape DTM’s MS and Mh computing functions g

and h, design a multi-tape DTM M that computes the function f which

is defined from functions g and h by primitive recursion.

Prove that every partial recursive function can be obtained from ini-

tial functions with a finite number of applications of composition and

primitive recursion operations and a single application of unbounded

minimization operation.