# Question regarding Cook-Levin theorem proof

I know a key part of the Cook-Levin theorem proof (as presented in the book by Sipser) is that given two rows of configurations, if the upper row is a valid configuration of a nondeterministic Turing machine $N$, and every 2×3 window is consistent with $N$, then the second row is either identical with the upper row or follows from it by a transition of $N$.

Would this still remain true if we were to replace the 2x3 window with a 2x2 window?

• Please don't disfigure your own posts. The question may be of interest to other visitors. (Note that if you want to delete a post of your you can do so by clicking "delete".) Nov 25, 2014 at 7:25
• You could even answer your own question if you know the answer. Maybe you'll learn even more!
– Juho
Nov 25, 2014 at 9:16

No, it would not. The reason is that the encoding of configurations might change in 3 consecutive places with a single transition. Specifically, this happens with transitions where the head moves to the left.

For example, consider the configuration $aabqcaa$, which means that the tape contains $aabcaa$ and the head is on $c$. Now, assume that we have the transition $\delta(q,c)=\{(s,d,L)\}$. So the $c$ should be replaced with $d$, the head should move left, and the state should change to $s$. Thus, the new configuration is $aasbdaa$. You can see that the change is in 3 consecutive places.

Had you only tracked changes is 2x2 windows, you should have allowed (for example) $qc$ to turn to $bd$, meaning that you allow the head to just "disappear".