4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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".) $\endgroup$
    – Raphael
    Commented Nov 25, 2014 at 7:25
  • $\begingroup$ You could even answer your own question if you know the answer. Maybe you'll learn even more! $\endgroup$
    – Juho
    Commented Nov 25, 2014 at 9:16

1 Answer 1

Reset to default
5
$\begingroup$

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".

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.