Problem Solving in Automata, Languages, and Complexity

(^206) TURING MACHINES What is wrong with the following proof of Example 4.25? We prove it by induction on n, as in Example 4. ...

4.7 Pairing Functions and G&lel Numberings 207 To do this, we introduce coding functions that encode several integers into o ...

208 TURING MACHINES 0 0 1 3 6 10 I ). 0 1 2 3 4 5 I Figure 4.18: The pairing function ~(i, j). and, hence, G is primitive recurs ...

4.7 Pairing Functions and G6del Numberings 209 Then, it is clear that r(item(n, l), item(n, 2)... , item(n, k)) = n. Thus, 7 is ...

210 TURING MACHINES (e) If 1 < - i < - size(n) and 1 < - l < - size(n) - i + 1, then we have subseq(n, iJ) = ( mint) ...

4.7 Pairing Functions and G6del Numberings 211 by the following segment of a pseudo-Pascal program (where the inputs to f are (n ...

212 TURING MACHINES Thus, from Theorem 4.37, sort is primitive recursive. (See also Exercise 4 of this section.) cl Solution 2. ...

4.7 Pairing Functions and G6del Numberings 213 3. 4. Let 121, n2,... , nk are k nonnegative integers. Prove that if 1 5 ii < ...

214 TURING MACHINES *10. functions. Show that the following function f is primitive recursive: f(o7 4 = s(n), f (m + 1, n> = ...

4.8 Partial Recursive Functions 215 Unbounded Minimization: Given a total predicate g : N”+l + (0, l}, define function f : N” + ...

216 TURING Example 4.39 Show that if a set A can be expressed as (3m)R(n, m)} for some recursive predicate R, then A is r.e. que ...

4.8 Partial Recursive Functions 217 Case 1. There exists an integer j, 0 < j < n, such that ij < k and it = k for alI e ...

218 TURING MACHlNES Based on the notion of lexicographic ordering and the function LX, we can extend the notion of partial recur ...

4.8 Partial Recursive Functions 219 (b) This can be proved by induction. For k = 1, concat~ is just the identity function. For k ...

220 TURING MACHINES Theorem 4.44 Every Turing-computable function is partial recursive. Proof. From Theorem 4.19, we know that i ...

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 ...

222 TURING MACHINES Theorem 4.47 Every partial recursive function is Turing-computable. Proof. From the above lemma, we know tha ...

4.8 Partial Recursive Functions 223 Minimization. Assume that g : N’“+l + N is a total predicate and that f(nl,... , nk) = (minm ...

224 TURING MACHINES 4. Show that the following functions defined on (a, b)* are primitive recur- sive: (a) fi(x,y) = [z is a sub ...

5 Computability Theory 5.1 Universal Turing Machines In this chapter, we study the general properties of computable functions an ...