# Computing snapshot of Turing machine from previous snapshots in logarithmic space?

To prove that $P \subseteq P_{\ poly}$ [see book by Arora and Barak, chapter 6, page no 105]

Proof : Let $M$ be an oblivious TM and running time is $T(n)$, let $x \in \{0,1\}^*$ be some input for $M$ and define the transcript of $M$'s execution on $x$ to be the sequence $z_1,z_2,..z_{T(n)}$ of snapshots (the machine's state and symbol read by all heads) of the execution at each step in time.

We can encode each such snapshot $z_i$ by a constant-sized binary string, and furthermore, we can compute the string $z_i$ based on input $x$, the previous snapshot $z_{i-1}$ and snapshot $z_{i_1},z_{i_2},\cdots ,z_{i_k}$, where $z_{i_j}$ denotes the last step that $M$ 's jth head was in the same position as it is in the ith step.

The composition of all these constant-sized circuits gives rise to circuit that computes from the input $x$ the snapshot $z_{T(n)}$. This requires polynomial space, but I want to do this whole computation in logarithmic space.

My question : How to compute snapshot $z_i$ of Turing machine $M$ from previous snapshots using logarithmic space?

1. Encode the state of the machine, the position of the head, and the tape. Computing a bit of the tape requires knowing whether the head is currently at that position or at a neighboring position. Since in general a polytime machine has a polysize tape, this requires circuits accessing $\Theta(\log n)$ inputs.