# 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".) – Raphael Nov 25 '14 at 7:25
• You could even answer your own question if you know the answer. Maybe you'll learn even more! – Juho Nov 25 '14 at 9:16

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".
{"ft_lang_label":"__label__en","ft_lang_prob":0.9429713,"math_prob":0.98029864,"size":444,"snap":"2020-24-2020-29","text_gpt3_token_len":109,"char_repetition_ratio":0.11590909,"word_repetition_ratio":0.0,"special_character_ratio":0.23198198,"punctuation_ratio":0.055555556,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9889468,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-05-30T09:59:03Z\",\"WARC-Record-ID\":\"<urn:uuid:74f6d699-a80f-417e-8844-fd522262ee2e>\",\"Content-Length\":\"139926\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:5b8aa878-5bcf-4494-8e8a-b176724966c0>\",\"WARC-Concurrent-To\":\"<urn:uuid:b927ad05-cb6c-4277-b6f4-ea2af241f55f>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/33495/question-regarding-cook-levin-theorem-proof\",\"WARC-Payload-Digest\":\"sha1:NWEZPBEM4YB42MHQB7EFPEYBSS2WX25R\",\"WARC-Block-Digest\":\"sha1:4Q333VNRGXMZYLIFXGQ46UOHAUICTWNK\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-24/CC-MAIN-2020-24_segments_1590347407667.28_warc_CC-MAIN-20200530071741-20200530101741-00116.warc.gz\"}"}