I'm trying to understand the proof of the Cook-Levin thereom in Aurora and Barak's "Computational Complexity" text.

A snapshot $z_i$ of $M$’s execution on some input $y$ at a particular step $i$ is the triple $(a, b, q_i) \in \Gamma \times \Gamma \times Q$ such that $a, b$ are the symbols read by $M$’s heads from the two tapes and $q$ is the state $M$ is in at the $i$th step.

At some point in the proof, it is claimed that $$z_i = F(z_{i-1}, z_{prev(i)}, y_{inputpos(i)}),$$ where

  • $z_i$ represents a snapshot of the the Turing machine at step $i$ when started on input $y$

  • $prev(i)$ denotes the last step before $i$ that $M$ visited the same location on its work tape,

  • $inputpos(i)$ denotes the location of the input tape head at the $i$th step

The assumptions are that $M$ has only two tapes and that it is oblivious.

My understanding is that on input $y$, the computation of $M$ can be described by a sequence of configurations that tell us the current tape symbols, the current register state. I think the claim is that the next snapshot, $z_i$, can be computed using only $z_{i-1}, z_{prev(i)}, y_{inputpos(i)}$ in our special case. How?

If $z_i=(a,b,q_i)$, then I think we can just set $a = y_{inputpos(i)}$ since $y_{inputpos(i)}$ is the content of the input work tape cell at step $i$. How do we deduce $b$ and $q_i$ from $(z_{i-1}, z_{prev(i)}, y_{inputpos(i)})$?

If $z_{i-1}$ tells us the current snapshot, why is this not sufficient to deduce the next one? Doesn't $M$'s transition function tell us this?

  • $\begingroup$ How would you know the next $a,b$ just from $z_{i-1}$? $\endgroup$ Sep 5, 2018 at 16:38
  • $\begingroup$ Ah, I see. The transition function of the TM tells us what to write in the current cells, but not what the contents will be after moving the tapes... $\endgroup$
    – theQman
    Sep 5, 2018 at 16:48


Your Answer

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