# Proof of the Cook-Levin Theorem - snapshot transitions

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?

• How would you know the next $a,b$ just from $z_{i-1}$? Commented Sep 5, 2018 at 16:38
• 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... Commented Sep 5, 2018 at 16:48