207 Complexity — Snapshot
207.1 Overview
This module develops the snapshots behind the Cook–Levin tableau of Arora–Barak [AB09, §2.3.4]. A snapshot of a multi-tape Turing machine at a given time is the constant-size record of its state and the symbols under its heads. The module defines snapshots, the head schedule of a machine on inputs of length \(n\) (read off from the all-zeros input \(0^n\)), the last-visit function on work-tape cells, and the finite local functions computing the next state, the symbol left in a cell, and the emitted output bit from a snapshot. Its main results show that for an oblivious machine computation is local: the snapshot at each time is determined by the previous snapshot, the input bit at the scheduled input position, and the snapshots at the last visits of the current work cells.
207.2 Declarations
Let \(M\) be a multi-tape Turing machine over the binary alphabet with a finite set \(Q\) of states and \(k\) work tapes, whose tape cells each hold a bit or the blank symbol \(\sqcup \). A snapshot of \(M\) is a triple \((q, a, b)\) consisting of a state \(q \in Q \cup \{ \bot \} \), where \(\bot \) marks a halted machine, an input symbol \(a \in \{ 0, 1, \sqcup \} \), and a tuple \(b = (b_0, \dots , b_{k-1})\) of work-tape symbols \(b_\tau \in \{ 0, 1, \sqcup \} \), one per work tape.
Let \(M\) be a binary multi-tape Turing machine with finite state set \(Q\) and \(k\) work tapes, let \(x \in \{ 0,1\} ^*\) and let \(t \in \mathbb {N}\). The snapshot of \(M\) on \(x\) at time \(t\) is the triple consisting of the state (\(\bot \) if halted), the symbol under the input head, and the \(k\) symbols under the work-tape heads, in the configuration reached by running \(M\) for \(t\) steps from its initial configuration on \(x\). Since a step leaves a halted configuration unchanged, this is defined at every time \(t\).
Let \(M\) be a binary multi-tape Turing machine and let \(n, t \in \mathbb {N}\). On an input of length \(n\) the input cells are numbered \(0, 1, \dots , n+1\), where cell \(p\) with \(1 \le p \le n\) holds the \(p\)-th input bit and cells \(0\) and \(n+1\) are blank boundary cells. The scheduled input position \(\mathrm{inpos}_M(n, t) \in \{ 0, \dots , n+1\} \) is the position of the input head after \(t\) steps of \(M\) on the all-zeros input \(0^n\).
Let \(M\) be a binary multi-tape Turing machine with \(k\) work tapes whose cells are indexed by \(\mathbb {Z}\), and let \(n, t \in \mathbb {N}\) and \(\tau \in \{ 0, \dots , k-1\} \). The scheduled work position \(\mathrm{wpos}_M(n, t, \tau ) \in \mathbb {Z}\) is the position of the head of work tape \(\tau \) after \(t\) steps of \(M\) on the all-zeros input \(0^n\).
Let \(M\) be a binary multi-tape Turing machine with \(k\) work tapes indexed by \(\mathbb {Z}\), let \(n, t \in \mathbb {N}\) and \(\tau \in \{ 0, \dots , k-1\} \), and for \(s \in \mathbb {N}\) let \(w(s)\) be the position of the head of work tape \(\tau \) after \(s\) steps of \(M\) on the all-zeros input \(0^n\). The last previous visit \(\mathrm{prev}_M(n, t, \tau )\) is the largest \(s \lt t\) with \(w(s) = w(t)\), and is undefined when no such \(s\) exists.
Let \(M\) be a binary multi-tape Turing machine with finite state set \(Q\), \(k\) work tapes and transition function \(\delta \), and let \((q, a, b)\) be a snapshot of \(M\), consisting of a state \(q \in Q \cup \{ \bot \} \) (\(\bot \) meaning halted), an input symbol \(a \in \{ 0, 1, \sqcup \} \) and work-tape symbols \(b = (b_0, \dots , b_{k-1})\) in \(\{ 0, 1, \sqcup \} \). Its successor state is \(\bot \) if \(q = \bot \), and otherwise the successor state in \(Q \cup \{ \bot \} \) prescribed by the transition \(\delta (q, a, b)\).
Let \(M\) be a binary multi-tape Turing machine with finite state set \(Q\), \(k\) work tapes and transition function \(\delta \), let \((q, a, b)\) be a snapshot of \(M\) (a state \(q \in Q \cup \{ \bot \} \) with \(\bot \) meaning halted, an input symbol \(a\), and work-tape symbols \(b_0, \dots , b_{k-1}\), all in \(\{ 0, 1, \sqcup \} \)), and let \(\tau \in \{ 0, \dots , k-1\} \). The symbol left under work head \(\tau \) is \(b_\tau \) if \(q = \bot \); if \(q \in Q\), it is the symbol in \(\{ 0, 1, \sqcup \} \) that the transition \(\delta (q, a, b)\) writes on work tape \(\tau \), or \(b_\tau \) when that transition writes nothing on tape \(\tau \).
Let \(M\) be a binary multi-tape Turing machine with finite state set \(Q\), \(k\) work tapes, an append-only output tape and transition function \(\delta \), and let \((q, a, b)\) be a snapshot of \(M\) (a state \(q \in Q \cup \{ \bot \} \) with \(\bot \) meaning halted, an input symbol \(a\), and work-tape symbols \(b\)). The emitted symbol of the snapshot is either a bit or nothing: it is nothing if \(q = \bot \), and otherwise it is the optional output bit that the transition \(\delta (q, a, b)\) appends to the output tape.
For a binary string \(x = x_1 x_2 \cdots x_n\) and a position \(p \in \mathbb {N}\), the input symbol of \(x\) at position \(p\) is the blank symbol \(\sqcup \) if \(p = 0\) or \(p \gt n\), and is the bit \(x_p\) if \(1 \le p \le n\).
Let \(M\) be a binary multi-tape Turing machine with \(k\) work tapes that is oblivious: for any two inputs of the same length and every \(t \in \mathbb {N}\), the input-head position and all work-head positions after \(t\) steps agree on the two inputs. Then for every input \(x \in \{ 0,1\} ^*\) and every \(t \in \mathbb {N}\), the input-head position after \(t\) steps of \(M\) on \(x\) equals the input-head position after \(t\) steps of \(M\) on the all-zeros input \(0^{|x|}\), and for every work tape \(\tau \) the head position of tape \(\tau \) after \(t\) steps on \(x\) equals its head position after \(t\) steps on \(0^{|x|}\).
Let \(M\) be a binary multi-tape Turing machine with initial state \(q_0\) and \(k\) work tapes, and let \(x \in \{ 0,1\} ^*\). Before any step is taken, \(M\) on input \(x\) is in state \(q_0\), the symbol under its input head is the first bit \(x_1\) of \(x\) (or the blank \(\sqcup \) if \(x\) is empty), and every one of its \(k\) work heads reads the blank \(\sqcup \).
Let \(M\) be a binary multi-tape Turing machine with finite state set \(Q\), \(k\) work tapes and transition function \(\delta \), let \(x \in \{ 0,1\} ^*\) and \(t \in \mathbb {N}\), and let \(q \in Q \cup \{ \bot \} \) (with \(\bot \) meaning halted), \(a\) and \(b = (b_0, \dots , b_{k-1})\) be the state, the symbol under the input head, and the symbols under the work heads after \(t\) steps of \(M\) on \(x\). Then the state of \(M\) on \(x\) after \(t + 1\) steps is \(\bot \) if \(q = \bot \), and otherwise is the successor state prescribed by the transition \(\delta (q, a, b)\).
Let \(M\) be a binary multi-tape Turing machine that is oblivious, meaning that on any two inputs of the same length its input-head and work-head positions after \(t\) steps agree for every \(t\). Let \(x = x_1 \cdots x_n \in \{ 0,1\} ^n\) and \(t \in \mathbb {N}\), number the input cells \(0, 1, \dots , n+1\) with cell \(i \in \{ 1, \dots , n\} \) holding the \(i\)-th input bit, and let \(p\) be the position of the input head after \(t\) steps of \(M\) on the all-zeros input \(0^n\). Then the symbol under the input head after \(t\) steps of \(M\) on \(x\) is the blank \(\sqcup \) if \(p = 0\) or \(p \gt n\), and is the bit \(x_p\) otherwise.
Let \(M\) be a binary multi-tape Turing machine with finite state set \(Q\), transition function \(\delta \) and \(k\) work tapes whose cells are indexed by \(\mathbb {Z}\); let \(x \in \{ 0,1\} ^*\), \(t \in \mathbb {N}\), \(\tau \in \{ 0, \dots , k-1\} \) and \(p \in \mathbb {Z}\). Let \(q \in Q \cup \{ \bot \} \) (with \(\bot \) meaning halted), \(a\) and \(b = (b_0, \dots , b_{k-1})\) be the state, the input-head symbol and the work-head symbols after \(t\) steps of \(M\) on \(x\), and let \(h\) be the position of the head of work tape \(\tau \) at that time. Then after \(t + 1\) steps, cell \(p\) of work tape \(\tau \) has the same content as after \(t\) steps if \(p \ne h\); if \(p = h\), its content is \(b_\tau \) when \(q = \bot \), and otherwise is the symbol that \(\delta (q, a, b)\) writes on tape \(\tau \), or \(b_\tau \) when that transition writes nothing on tape \(\tau \).
Let \(M\) be a binary multi-tape Turing machine with \(k\) work tapes whose cells are indexed by \(\mathbb {Z}\), let \(x \in \{ 0,1\} ^*\), \(\tau \in \{ 0, \dots , k-1\} \), \(p \in \mathbb {Z}\), and let \(a \le b\) be natural numbers. If for every \(r\) with \(a \le r \lt b\) the head of work tape \(\tau \) is not at cell \(p\) after \(r\) steps of \(M\) on \(x\), then the content of cell \(p\) of work tape \(\tau \) after \(b\) steps of \(M\) on \(x\) equals its content after \(a\) steps.
Let \(M\) be a binary multi-tape Turing machine with \(k\) work tapes indexed by \(\mathbb {Z}\), let \(n, t \in \mathbb {N}\) and \(\tau \in \{ 0, \dots , k-1\} \), and for \(s \in \mathbb {N}\) let \(w(s)\) be the position of the head of work tape \(\tau \) after \(s\) steps of \(M\) on the all-zeros input \(0^n\), and let \(\mathrm{prev}\) be the largest \(s \lt t\) with \(w(s) = w(t)\), undefined when there is no such \(s\). If \(\mathrm{prev}\) is undefined, then \(w(r) \ne w(t)\) for every \(r \lt t\).
Let \(M\) be a binary multi-tape Turing machine with \(k\) work tapes indexed by \(\mathbb {Z}\), let \(n, t \in \mathbb {N}\) and \(\tau \in \{ 0, \dots , k-1\} \), and for \(s \in \mathbb {N}\) let \(w(s)\) be the position of the head of work tape \(\tau \) after \(s\) steps of \(M\) on the all-zeros input \(0^n\), and let \(\mathrm{prev}\) be the largest \(s \lt t\) with \(w(s) = w(t)\), undefined when there is no such \(s\). If \(\mathrm{prev}\) is defined and equals \(s\), then \(s \lt t\), \(w(s) = w(t)\), and \(w(r) \ne w(t)\) for every \(r\) with \(s \lt r \lt t\).
Let \(M\) be a binary multi-tape Turing machine with finite state set \(Q\), transition function \(\delta \) and \(k\) work tapes indexed by \(\mathbb {Z}\), which is oblivious: on any two inputs of the same length its input-head and work-head positions after \(t\) steps agree for every \(t\). Let \(x \in \{ 0,1\} ^n\), \(t \in \mathbb {N}\) and \(\tau \in \{ 0, \dots , k-1\} \), and let \(w(s)\) be the position of the head of work tape \(\tau \) after \(s\) steps of \(M\) on \(0^n\). If no \(s \lt t\) has \(w(s) = w(t)\), then the symbol under head \(\tau \) after \(t\) steps of \(M\) on \(x\) is the blank \(\sqcup \). Otherwise let \(s\) be the largest such time and let \(q \in Q \cup \{ \bot \} \) (with \(\bot \) meaning halted), \(a\) and \(b = (b_0, \dots , b_{k-1})\) be the state, the input-head symbol and the work-head symbols after \(s\) steps of \(M\) on \(x\); then the symbol under head \(\tau \) after \(t\) steps of \(M\) on \(x\) is \(b_\tau \) if \(q = \bot \), and otherwise is the symbol that \(\delta (q, a, b)\) writes on tape \(\tau \), or \(b_\tau \) if that transition writes nothing on tape \(\tau \).