Read the remaining portion of Sipser § 7.4: pages 304 – 311
- Windows are used in the φmove formula of the proof of the Cook-Levine theorem. What does this boolean formula capture?
- Suppose that we are translating the Turing machine M1 from figure 3.10 of the text (pp. 173 in the third edition) to a boolean formula according to Cook-Levine. Suppose that the current configuration $$C_i$$ under consideration is
$$x x q_3 1 0 \# xx00 .$$
(Recall that a configuration represents the current contents of the tape, the current state, and the position of the tape head.)
Describe (a) a legal window involving configurations $$C_i,$$ and the next configuration $$C_{i+1}.$$and (b) an illegal window involving these configurations.
