Problem Solving in Automata, Languages, and Complexity

166 TURING MACHINES 4.2 Examples of Turing Machines We present some examples of Turing-computable functions and Turing- acceptab ...

4.2 Examples of Turing Machines 167 (3) In the ith i eration t of the loop, A& reads a symbol 2,+1-i at state 41 and, depend ...

168 TURING MACHINES Figure 4.4: DTM of Example 4.4. Example 4.5 Show thut {wwR ] w E {O,l}*} is Turing-decidable. Solution. This ...

4.2 Examples of Turing Machines 169 l/O, R B/O,R / B/O,R $/B, L^6 O/B, l/B, L L k? O/O, l/O, R R Figure 4.5: DTM of Example 4.5. ...

170 TURING MACHINES l/l1 R B/B, L l/B, R B/ 1,L B/B, L l/B, L l/l, R Figure 4.7: DTM computing the function sub. Solution. This ...

4.2 Examples of Turing Machines B/B, L B/B, R B/B,L l/B, L Figure 4.8: Procedure E. Solzsti~n. We create two procedures. The fir ...

172 TURING MACHINES B/B, L jg k-i+3 T cdB,R w / 1 '\ B / CI, L Figure 4.9: DTM M computing the function insert;. Solution. We cr ...

4.2 Examples of Turing Machines 173 Read-Only Turing Machines. In Theorem 4.2, we showed that every regular language is Turing-a ...

(^174) TURING MACHINES B (^0 0 1 1) B s-p-q-q-q-q -J Figure 4.10: Crossing sequences. For this DTM A& we show in Figure 4.10 ...

4.2 Examples of Turing Machines 175 sequence Si between the boundary of Ci- 1 and Ci , reads the symbol a in cell Ci, and nondet ...

176 TURING MACHINES (3) Sequences S and T are consistent sequences in QR, because S(p, 0) = (Q, 0, R) and So amd Tl are consiste ...

4.2 Examples of Turing Machines 177 Next, we argue that these configurations, when arranged in the right order, form the computa ...

178 TURING MACHINES (c) {umbnck 1 m > n > k > 0). (d) {cPPc~+~ I;,u$ 07. (e) {W E {a, b)* 1 Sita > #b(w)}, where #a( ...

4.2 Examples of Turing Machines 179 * 8. We consider an extension of read-only DTM’s. A one-pebble, read-only DTM (or, simply, o ...

180 10 4.3 TURING MACHINES (a) Consider the language L1 over the alphabet (C U {B}) x F, where F is the set of all partial funct ...

4.3 Multi-Tape Turing Machines 181 Figure 4.11: A two-way infinite one-tape DTM. to use, the class of Turing-computable function ...

182 TURING MACHINES Figure 4.12: The two tracks of a one-tape DTM. will simulate the right-hand part of the two-way tape of A&am ...

4.3 Multi-Tape Turing Machines 183 additional instructions: B’(qb, B) = (q;, [B,$ -f% S’(q;, B) = (qb,B, L), S’(qt,B) = (q;> ...

184 TURING MACHINES Figure 4.13: A three-tape DTM. Example 4.12 Find a three-tape DTM M that computes the function f (n, m) = n. ...

4.3 Multi-Tape Turing Machines^185 tape 1 head 1 tape 2 head 2 tape 3 head 3 Figure 4.14: The TM A& Next, we present a simul ...