Problem Solving in Automata, Languages, and Complexity

186 TURING MACHINES Then, A41 simulates each move of A4 as follows: We assume that after each simulation step, A41 is scanning a ...

4.3 Multi-Tape Turing Machines 187 61 (Q?y?, [a, x, b, B, c, xl) = (Qayc, [a, x, 4 4 c> Xl> L)T s (4 I x??, [a,B,b,X,c,X]) ...

Let us define such a machine more precisely: An infinite-tape DTM A& = (Q, C, I’., 6, s) has finitely many states and infini ...

4.3 Multi-Tape Turing Machines 189 Describe the details of a simulation step of the two-way DTM &+!I of Theorem 4.13 that s ...

190 TURING MACHINES Figure 4.15: A two-dimensional DTM. tape head tape head ( > a 00 Figure 4.16: Configuration change of ...

4.4 Church-Turing Thesis 191 4.4 Church-Turing Thesis From the equivalence results of the last section, it is plausible to conje ...

192 TURING MACHINES the same as the class of Turing-computable functions. In general, we a computational model reasonable if it ...

4.5 Unrestricted Grammars 193 Instruction Meaning READ(&) read the next input integer into Ri WRITE(Ri) write c( Ri) on the ...

194 TUIUNG MACHINES finite set of terminal symbols, with C n V = 8, S E V is the starting symbol, and R is a finite set of produ ...

4.5 Unrestricted Grammars 195 of C’s Note that, using our grammar G, we are not able to change any B to b before moving it to th ...

196 TURING MACHINES w [ R2(IR], where $ is the string w with symbol a replaced by A and symbol 6 replaced by B. Next, it uses sy ...

4.5 Unrestricted Grammars 197 5’ 3 [A] 3 [uaA] a [auB] % [aubbbB] 3 [uabbbL] % [ Luubbb] a a [ Rbubbb] a a [ uRbbbb] 3 a [ ubR,b ...

198 TURING MACHINES Theorem 4.20 If a language L C - C* is Turing-acceptable, then L = L(G) for some grammar G. Proof. We assume ...

4.5 Unrestricted Grammars 199 Construct grammars for each of the following languages. Also show (i) the derivation of the given ...

200 TURING MACHINES halts with output w. (In particular, if the current instruction label is Li, with i greater than the number ...

4.6 Primitive Recursive Functions^201 We say f is the function obtained from g and h by the operation of primitive recursion. Th ...

202 TURING MACHINES Example 4.24 Show that the function minus : N2 -+ N, defined by minus(m, n) = m 2 n = 1 0 ifm<n, - m -n i ...

4.6 Primitive Recursive Functions^203 Example 4.26 Show that the following functions are primitive recursive: ifx > - 1, if x ...

204 TURING MACHINES We now define three more operations on functions that preserve primitive recursiveness. We call a total func ...

4.6 Primitive Recursive Functions^205 Solution. (a) quot(m, n) = [if n > 0 then (mini)a+# - + 1) l n > m] else 01. (b) mod ...