Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 13] FINITE STATE MACHINES AND TURING MACHINES 335

Fig. 13-7

TURING MACHINES

13.14. LetMbe a Turing machine. Determine the pictureαcorresponding to each situation:

(a) Mis in states 2 and scanning the third letter of the tape expressionw=abbaa.

(b)Mis in states 3 and scanning the last letter of the tape expressionw=aabb.

(c) The input is the wordW=a^3 b^3.

(d) The input is the tape expressionW=〈( 3 , 2 )〉.

13.15. Supposeα=abs 2 aais a picture. Findβsuch thatα→βif the Turing machineMhas the quintuple
qwhere:

(a) q=s 2 abs 1 R; (b)q=s 2 aas 3 L; (c)q=s 2 abs 2 R;

(d)q=s 2 abs 3 L; (e)q=s 3 abs 2 R; (f)q=s 2 aas 2 L.

13.16. Repeat Problem 13.15 for the pictureα=s 2 aBab.

13.17. Find distinct picturesα 1 ,α 2 ,α 3 ,α 4 and a Turing machineMsuch that the following sequence does not
terminate:
α 1 →α 2 →α 3 →α 4 →α 1 →α 2 →···

13.18. Supposeα→β 1 andα→β 2 Mustβ 1 →β 2?

13.19. Supposeα=α(W)for some inputW, and supposeα→β→α. CanMrecognizeW?

13.20. LetA={a, b}. Find a Turing machineMwhich recognizes the languageL={abn|n> 0 }, that is,
whereLconsists of all wordsWbeginning with oneaand followed by one or morebs.

13.21. LetA={a, b}. FindaTuring machineMwhich recognizes the finite languageL={a, a^2 }, that is,
whereLconsists of the first two nonzero powers ofa.

COMPUTABLE FUNCTIONS

13.22. Find〈m〉if: (a)m=6; (b)m=( 5 , 0 , 3 , 1 ); (c)m=( 0 , 0 , 0 ); (d)m=( 2 , 3 ,− 1 ).

13.23.Find [E] for the expressions: (a)E= 111 s 2 aa 1 B111; (b)E=a 11 bs 1 Bb; (c)E=〈m〉wherem=

( 2 , 5 , 4 ).