《计算机科学导论原书第二版答案第十七章》由会员分享，可在线阅读，更多相关《计算机科学导论原书第二版答案第十七章（7页珍藏版）》请在金锄头文库上搜索。
1、1 CHAPTER 17 Theory of Computation (Solutions to Practice Set) Review Questions 1. The three statements in our Simple Language are the increment statement, decre- ment statement, and loop statement. The increment statement adds 1 to the vari- able; the decrement statement subtracts 1 from the variab
2、le; the loop statement repeats an action (or a series of actions) while the value of the variable is not zero. 2. Algorithm S17.1 shows how we implement Y X. 3. A problem that can be solved by our Simple Language can also be solved by the Turing machine. 4. A Turing machine is made of three componen
3、ts: a tape, a controller, and a read/ write head. The tape, at any one time, holds a sequence of characters from the set of characters acceptable by the machine; the read/write head at any moment points to one symbol on the tape and is used to read and write characters; the controller controls the r
4、ead/write head and is the theoretical counterpart of the central pro- cessing unit (CPU) in modern computers. 5. One way to delimit the data on a Turing machine tape is the use of two blanks, one at the beginning of the data and one at the end of the data. 6. The read/write head can move to left, ri
5、ght, or stay at the same place. At the same time, it may go to different state or remain in the same state. 7. A transition state diagram is a pictorial representation of a program written for the Turing machine. Algorithm S17.1Question 2 Y 0 while (X) decr (X) incr (Y) 2 8. Both tools show the same
6、 thing. The first uses a diagram; the second uses a table. 9. A Gdel number is an unsigned integer that is assigned to every program that can be written in a specific language. In the halting program, we represent a program as its Godel number when that program is the input to another program. 10. A
7、 polynomial solvable problem can be solved by a computer in a feasible time period. A non-polynomial solvable still can be solved by a computer, but not in an acceptable period of time. Multiple-Choice Questions Exercises 28. See Algorithm S17.2. 29. See Algorithm S17.3. After assigning Y to Z, we i
8、ncrement Z (X times). 11. a12. c13. b14. d15. a16. d 17. c18. b19. d20. c21. c22. a 23. c24. d25. c26. b27. d Algorithm S17.2Exercise 28 Temp 0 Y 0 while (X) decr (X) incr (Y) incr (Temp) while (Temp) decr (Temp) incr (X) Algorithm S17.3Exercise 29 Temp X Z Y / See solution to Exercise 28 / See solu
9、tion to Exercise 28 while (Temp) decr (Temp) incr (Z) 3 30. See Algorithm S17.4. 31. See Algorithm S17.5. 32. See Algorithm S17.6. We assume that Y X. 33. See Algorithm S17.7. Algorithm S17.4Exercise 30 Temp X Z 0 / See solution to Exercise 28 while (Temp) decr (Temp) Z Z + Y / See algorithm 17.7 in
10、 the text Algorithm S17.5Exercise 31 Temp X Z 1 / See solution to Exercise 28 while (Temp) decr (Temp) Z Z Y / See algorithm 17.8 in the text Algorithm S17.6Exercise 32 while (X) decr (X) decr (Y) Algorithm S17.7Exercise 33 Temp X + 1 while (X) decr (X) A1 Temp 0 while (Temp) decr (Temp) A2 4 34. Th
11、e machine with the single instruction (A, 1, b, R, B) cannot perform any action when it is in the state shown in the text. It crashes. 35. The tape moves to the right and goes to state B as shown below: 36. The machine goes through the following states: The last statement is the same as the first st
12、atement. The machine goes through an endless loop from statement 1 through statement 9. 37. Figure S17.37 shows the state diagram. b111bState: B Startb111bState: A 1b111bState: B 2b#11bState: B 3b#1bState: B 4b#bState: B 5b#bState: C 6b#1bState: C 7b#11bState: C 8b111bState: C 9b111bState: B Figure
13、S17.37Exercise 37 b/b/L 0/1/L 0/1/L 0/0/L 1/1/L b/b/N b/b/R b/1/L S1 : starting S2 : moving right S3 : add S4 : take care of carry S5 : moving left S6 : halt 1/0/L 1/0/L 1/1/R0/0/R S2 S4S5S6 S3S1 5 38. 39. 40. a. (S1, b, b, R, S2) S1 is the starting state. b. (S2, b, b, N, S3) If X = 0, then go to s
14、tate S3 (halt). c. (S2, 1, #, R, MR) X is decremented and blank is replaced by #. d. (MR, 1, 1, R, MR) MR is the move right state. e. (MR, b, b, N, BS) BS is the start of body loop state. f. (BH, b, b, L, ML) BH is the halt of body loop state. g. (ML, 1, 1, L, ML) ML is the move left state. h. (ML,
15、#, #, L, ML) i. (ML, b, b, N, S1) At the end of the program the number of #s shows the value of X. 41. a. (S1, b, b, R, S2) S1 is the starting state. b. (S2, 1, 1, R, S2) S2 is the move right state. c. (S2, b, b, L, S3) d. (S3, 1, b, L, S3) S3 is the move left state. 1 is changed to b. e. (S3, b, b,
16、 N, S4) S4 is the halt state. 42. a. (S1, b, b, R, S2) S1 is the starting state. b. (S2, b, b, N, S3) S3 is the halt state. c. (S2, 1, b, R, MR) S2 is the decrement X state. StartbbbbState: S1 X = 0 (S1, b, b, R, S2)bbbbState: S2 X = 0 (S2, b, 1, L, S3)bb1bState: S3 (halt) X = 1 StartbbbbState: S1 X = 0
