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

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

}

17秋学期《计算机科学导论》在线作业.txt
17秋学期《计算机科学导论》在线作业 1. 计算机中操作系统的任务包括 A. 进程调度 B. 内存管理 C. 文件管理 D. 总线管理 正确答案: ABC 满分:2 分 得分: ...

《计算机科学导论》课后练习(翻译).doc