5. [14 marks] This question studies the proof of Savitch's theorem. You may assume the TM...

 

Transcribed Image Text:

5. [14 marks] This question studies the proof of Savitch's theorem. You may assume the TM M in the proof can compute function f(n) in the proof in O(f(n)) space. (a) [2 marks] In words, give a high-level overview of how the proof of Savitch's theorem works. (b) [6 marks] The CANYIELD procedure in the proof has 6 steps: Describe in a sentence or two the purpose of each step. (c) [2 marks] Why does the machine M in the proof correctly simulate the NTM N? (d) [4 marks] Why does M use O(f2(n)) space? 5. [14 marks] This question studies the proof of Savitch's theorem. You may assume the TM M in the proof can compute function f(n) in the proof in O(f(n)) space. (a) [2 marks] In words, give a high-level overview of how the proof of Savitch's theorem works. (b) [6 marks] The CANYIELD procedure in the proof has 6 steps: Describe in a sentence or two the purpose of each step. (c) [2 marks] Why does the machine M in the proof correctly simulate the NTM N? (d) [4 marks] Why does M use O(f2(n)) space?