当前位置:首页 >> 理学 >>

计算机科学导论原书第二版答案第十七章


CHAPTER 17

Theory of Computation
(Solutions to Practice Set)

Review Questions
1. The three statements in our Simple Language are the increment statement, decrement statement, and loop statement. The increment statement adds 1 to the variable; the decrement statement subtracts 1 from the variable; 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. Algorithm S17.1 Question 2
Y←0 while (X)

{
decr (X) incr (Y) }

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 components: 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 read/write head and is the theoretical counterpart of the central processing 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, right, 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.
1

2

8. Both tools show the same thing. The first uses a diagram; the second uses a table. 9. A G?del 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 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
11. a 17. c 23. c 12. c 18. b 24. d 13. b 19. d 25. c 14. d 20. c 26. b 15. a 21. c 27. d 16. d 22. a

Exercises
28. See Algorithm S17.2. Algorithm S17.2 Exercise 28
Temp ← 0 Y←0 while (X) { decr (X) incr (Y) incr (Temp) } while (Temp) { decr (Temp) incr (X) }

29. See Algorithm S17.3. After assigning Y to Z, we increment Z (X times). Algorithm S17.3 Exercise 29
Temp ← X Z←Y while (Temp) // See solution to Exercise 28 // See solution to Exercise 28

{
decr (Temp) incr (Z)

}

3

30. See Algorithm S17.4. Algorithm S17.4 Exercise 30
Temp ← X Z←0 while (Temp) // See solution to Exercise 28

{
decr (Temp) Z←Z+Y // See algorithm 17.7 in the text

} 31. See Algorithm S17.5. Algorithm S17.5 Exercise 31
Temp ← X Z←1 while (Temp) // See solution to Exercise 28

{
decr (Temp) Z←Z×Y // See algorithm 17.8 in the text

} 32. See Algorithm S17.6. We assume that Y > X. Algorithm S17.6 Exercise 32
while (X)

{
decr (X) decr (Y)

} 33. See Algorithm S17.7. Algorithm S17.7 Exercise 33
Temp ← X + 1 while (X)

{
decr (X) A1 Temp ← 0

}
while (Temp)

{ }
decr (Temp) A2

4

34. The 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 ↓
b 1 1 1 b State: B

as shown below:

36. The machine goes through the following states:
Start 1 2 3 4 5 6 7 8 9 ↓ b b b b b b b b ↓ b b 1 ↓ 1 # # # # # ↓ # 1 ↓ 1 1 1 ↓ 1 # # # ↓ # 1 1 1 1 1 1 ↓ 1 # ↓ # 1 1 1 1 b b b b ↓ b b b b b b State: A State: B State: B State: B State: B State: C State: C State: C State: C State: B

The last statement is the same as the first statement. The machine goes through an endless loop from statement 1 through statement 9. 37. Figure S17.37 shows the state diagram. Figure S17.37 Exercise 37
1/1/R S1 b/b/R S2 0/0/R b/b/L 1/0/L 1/0/L S4 0/0/L 0/1/L 1/1/L S5 0/1/L S3

b/1/L S1 : starting S4 : take care of carry

b/b/N S3 : add S6 : halt

S6

S2 : moving right S5 : moving left

5

38.
Start

… b
X=0


b b b

… … …

State: S1

(S1, b, b, R, S2) (S2, b, 1, L, S3)

… b
X=0


b b b

State: S2 State: S3 (halt)

… b
X=1


b 1 b

39.
Start

… b
X=0


b b b

… … …

State: S1 State: S2 State: S3 (halt)

(S1, b, b, R, S2) (S2, b, b, N, S3)

… b
X=0


b b b

… b
X=0


b b b

40. a. (S1, b, b, R, S2) ? S1 is the starting state. b. (S2, b, b, N, S3) ? If X = 0, then go to state 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, #, #, 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. b. c. d. e. 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. (S1, b, b, R, S2) ? S1 is the starting state. (S2, 1, 1, R, S2) ? S2 is the move right state. (S2, b, b, L, S3) (S3, 1, b, L, S3) ? S3 is the move left state. 1 is changed to b. (S3, b, b, N, S4) ? S4 is the halt state.

6

d. (MR, 1, 1, R, MR) ? MR is the move right state. e. (MR, b, b, N, S4) ? S4 is the start loop body state. f. (S4, b, b, R, S5) ? S5 is the increment Y state. g. (S5, 1, 1, R, S5) h. (S5, b, 1, L, S6) ? S6 is the end loop body state. i. (S6, 1, 1, L, S6) ? S6 is the end loop body state. j. (S6, b, b, L, ML) ? ML is the move left state. k. (ML, 1, 1, L, ML) l. (ML, b, b, N, S1) 43. We use a single 1 to represent 0, two 1’s to represent 1, three 1’s to represent 2, …, and n + 1 1’s to represent n. 44. The following table shows the statements for the macro X ← 0 and the G?del number for each statement Algorithm S17.8
while X1

{
decr X1

}

// G?del Number: CF1 // G?del Number: D // G?del Number: BF1 // G?del Number: E

The G?del number for the macro is then (CF1DBF1E)16. Notice that this micro does not preserve the value of X1. The G?del number for the macro will be longer if we want to preserve X1. 45. The following table shows the statements for the macro and the G?del number for each statement. Algorithm S17.9
X2 ← 0 incr X2 incr X2 // G?del Number: CF2DBF2E // G?del Number: AF2 // G?del Number: AF2

The G?del number for the macro is then (CF2DBF2EAF2AF2)16. Notice that this micro does not preserve the value of X2. The G?del number for the macro will be longer if we want to preserve X2. 46. The following table shows the statements. The G?del number for the macro is (CF3DBF3ECF1DBF1AF3ECF2DBF2AF3E)16. Notice that this micro does not preserve the value of X1 or X2 The G?del number for the macro will be longer if we want to preserve these two values.

7

Algorithm S17.10
X3 ← 0 while X1 // G?del Number: CF3DBF3E // G?del Number: CF1 // G?del Number: D // G?del Number: BF1 // G?del Number: AF3 // G?del Number: E // G?del Number: CF2 // G?del Number: D // G?del Number: BF2 // G?del Number: AF3 // G?del Number: E

{
decr X1 incr X3

}
while X2

{
decr X2 incr X3

}


相关文章:
计算机科学导论原书第二版答案第十七章.pdf
计算机科学导论原书第二版答案第十七章 - CHAPTER 17 Theory o
计算机科学导论原书第二版答案第十八章.pdf
计算机科学导论原书第二版答案第十八章 - CHAPTER 18 Artifici
计算机科学导论原书第二版答案第二章.pdf
计算机科学导论原书第二版答案第 - CHAPTER 2 Number Sys
计算机科学导论原书第二版答案第十四章.pdf
计算机科学导论原书第二版答案第十四章 - CHAPTER 14 Database
计算机科学导论原书第二版答案第十一章.pdf
计算机科学导论原书第二版答案第十一章 - CHAPTER 11 Data Str
计算机科学导论原书第二版答案第七章.pdf
计算机科学导论原书第二版答案第七章 - CHAPTER 7 Operating
计算机科学导论原书第二版答案第十六章.pdf
计算机科学导论原书第二版答案第十六章 - CHAPTER 16 Security
计算机科学导论原书第二版答案第十二章.pdf
计算机科学导论原书第二版答案第十二章 - CHAPTER 12 Abstract
计算机科学导论原书第二版答案第九章.pdf
计算机科学导论原书第二版答案第九章 - CHAPTER 9 Programmin
计算机科学导论原书第二版答案第十五章.pdf
计算机科学导论原书第二版答案第十五章 - CHAPTER 15 Data Com
计算机科学导论原书第二版答案第十三章.pdf
计算机科学导论原书第二版答案第十三章 - CHAPTER 13 File Str
计算机科学导论习题答案.pdf
计算机科学导论习题答案_IT/计算机_专业资料。计算机科学导论习题答案 原书第二版 英文 CHAPTER 1 Introduction (Solutions to Practice Set) Review Questions 1. ...
计算机科学导论第2章-答案.doc
计算机科学导论第2章-答案 - 第 2 章 计算机体系结构与组织 习题(答案) 一. 选择题 1.D 5.C 6.B 10.C 11.A 15.A 16.A 17.B 18.A 12.C 13....
大学计算机基础课课本计算机科学导论课后答案.doc
自己综合汇总的计算机科学导论第二版课后答案 ...第八章 算法 16 D 17 C 18 C 19 B 20 A ...(4)定义方法 6 见导论书 165 页 7 见导论书 ...
计算机科学导论习题答案.txt
计算机科学导论习题答案 - 计算机科学导论习题答案 第一章 一.选择题 1-5 A D B D D 二.填空题 【1】 处理信息快、存储容量大、可靠性高、准确性高 【2...
计算机科学导论习题答案.doc
计算机科学导论习题答案_工学_高等教育_教育专区。...第八章 算法 16 D 17 C 18 C 19 B 20 A ...(4)定义方法 6 见导论书 165 页 7 见导论书 ...
《计算机科学导论》课后练习(翻译).doc
计算机科学导论》课后练习(翻译)_理学_高等教育_...也就是在第二代计算机末期和第三代 计算机初期出现...A.位图 B.矢量图 C.余码系统 D.答案 A 或 B...
计算机科学导论 (第二版 清华大学出版社)第12章 社会和....doc
计算机科学导论 (第二版 清华大学出版社)第12章 社会和职业问题(答案)_工学_高等教育_教育专区。第二版 清华大学出版社 第12 章 社会和职业问题习题(答案) ...
计算机科学导论答案第一章.pdf
计算机科学导论答案第一章_工学_高等教育_教育专区。计算机科学与导论机械工业出版社原书第版答案第一章 CHAPTER 1 Introduction (Solutions to Review Questions ...
计算机科学导论 第二次作业-答案.doc
计算机科学导论 第二次作业-答案 - 1 计算机内存容量为 512MB,它一共有