152 Complexity — Examples
152.1 Overview
This module is the sanity check that the Turing-machine model and the class definitions are usable: it defines the language of binary palindromes, constructs an explicit three-state one-work-tape machine that decides it, and proves that the language lies in \(\mathrm{DTIME}(n+1)\) and hence in \(\mathsf{P}\) (Arora–Barak, Examples 1.1 and 1.4).
152.2 Declarations
The language of binary palindromes: the set of finite words \(x \in \{ 0,1\} ^*\) that equal their own reversal, \(x^{R} = x\).
A concrete Turing machine over the binary alphabet with one work tape and three control states \(\{ 0,1,2\} \), given by an explicit transition table. State \(0\) (copy) copies each input bit to the work tape while moving both heads right; upon reading the blank past the input it switches to state \(1\) (rewind), which moves the input head back left to the left boundary; state \(2\) (test) then moves the input head right and the work head left in unison, comparing the two scanned symbols, emitting false and halting on any mismatch and emitting true when the input is exhausted with all pairs matched.
Given a binary word \(x\), a time bound \(t \in \mathbb {N}\), and an integer cell index \(z\), this is the partial tape content whose cell \(z\) holds the bit \(x_z\) when \(0 \le z \lt t\) (and \(z\) is within \(x\)), and is blank otherwise. It describes a work tape onto which exactly the first \(t\) bits of \(x\) have been copied.
For a binary word \(x\) of length \(n\), a control state \(q \in \{ 0,1,2\} \), an input head position \(p \in \{ 0,\dots ,n+1\} \) (cells \(1\) through \(n\) hold the input bits, cells \(0\) and \(n+1\) are blank boundary cells), an integer work head position \(w\), and a time bound \(t\), this is the machine configuration in live state \(q\) with input head at \(p\), work tape holding exactly the first \(t\) bits of \(x\) in cells \(0,\dots ,t-1\) (all other cells blank), work head at \(w\), and empty output. These are the configurations appearing in the three phase invariants.
Let \(x\) be a binary word and \(t \lt |x|\). Updating the partial tape that holds the first \(t\) bits of \(x\) (in cells \(0,\dots ,t-1\), blank elsewhere) by writing the bit \(x_t\) into cell \(t\) yields exactly the partial tape holding the first \(t+1\) bits of \(x\).
Let \(x\) be a binary word and \(t \lt |x|\). From the configuration of the three-state palindrome machine on input \(x\) in copy state with input head at cell \(t+1\) (scanning \(x_t\)), the first \(t\) bits copied to the work tape, and work head at cell \(t\), one transition writes \(x_t\) at the work head and advances both heads: it yields the copy-state configuration with input head at \(t+2\), the first \(t+1\) bits copied, and work head at \(t+1\).
Let \(x\) be a binary word. For every \(t \le |x|\), running the three-state palindrome machine for \(t\) steps from its initial configuration on input \(x\) reaches the copy-state configuration with input head at cell \(t+1\), exactly the first \(t\) bits of \(x\) copied onto the work tape (every other work cell still blank), and work head at cell \(t\).
Let \(x\) be a binary word of length \(n\). From the configuration of the three-state palindrome machine on input \(x\) in copy state with the input head on the right boundary blank (cell \(n+1\)), all \(n\) bits copied, and work head at cell \(n\), one transition switches to the rewind state and moves the input head left to cell \(n\), leaving the work tape and the work head unchanged.
Let \(x\) be a binary word of length \(n\) and \(i \lt n\). From the configuration of the three-state palindrome machine on input \(x\) in rewind state with input head at cell \(i+1\), all \(n\) bits copied, and work head at cell \(n\), one transition moves the input head left to cell \(i\) and changes nothing else: the state, the copied work tape, and the work head position are preserved.
Let \(x\) be a binary word of length \(n\). For every \(i \le n\), running the three-state palindrome machine for \(i\) steps from the rewind-state configuration on input \(x\) with input head at cell \(i\), all \(n\) bits copied, and work head at cell \(n\) brings the input head to the left boundary cell \(0\), with the state, work tape, and work head unchanged.
Let \(x\) be a binary word of length \(n\). From the configuration of the three-state palindrome machine on input \(x\) in rewind state with the input head on the left boundary blank (cell \(0\)), all \(n\) bits copied, and work head at cell \(n\), one transition switches to the test state, moves the input head right to cell \(1\), and moves the work head left to the integer cell \(n-1\) (which is \(-1\) when \(x\) is empty), leaving the work tape unchanged.
Let \(x\) be a binary word of length \(n\) and \(i \lt n\). In the test-state configuration of the palindrome machine on input \(x\) with input head at cell \(i+1\), all \(n\) bits copied, and work head at the integer cell \(n-1-i\), the symbol under the work head is the \(i\)-th bit of the reversal \(x^{R}\).
Let \(x\) be a binary word of length \(n\) and \(i \lt n\), and suppose the \(i\)-th bit of the reversal \(x^{R}\) equals the \(i\)-th bit of \(x\). From the test-state configuration of the palindrome machine on input \(x\) with input head at cell \(i+1\), all \(n\) bits copied, and work head at the integer cell \(n-1-i\), one transition advances the opposing heads: the input head moves right to cell \(i+2\) and the work head moves left to cell \(n-1-(i+1)\), with state and work tape unchanged.
For a binary word \(x\) and an index \(i\), the predicate asserting that every opposing pair at or after position \(i\) agrees: for all \(j\) with \(i \le j \lt |x|\), the \(j\)-th bit of the reversal \(x^{R}\) equals the \(j\)-th bit of \(x\).
Let \(x\) be a binary word and \(i \lt |x|\) an index at which the \(i\)-th bit of the reversal \(x^{R}\) equals the \(i\)-th bit of \(x\). Then all opposing pairs of \(x\) at or after position \(i\) agree if and only if all opposing pairs at or after position \(i+1\) agree.
Let \(x\) be a binary word of length \(n\), and let \(r\) and \(i \le n\) satisfy \(n = i + r\). Running the three-state palindrome machine for \(r+1\) steps from the test-state configuration on input \(x\) with input head at cell \(i+1\), all \(n\) bits copied, and work head at the integer cell \(n-1-i\) produces a halted configuration whose output is the single bit true if every opposing pair of \(x\) at or after position \(i\) agrees (the \(j\)-th bit of \(x^{R}\) equals the \(j\)-th bit of \(x\) for all \(i \le j \lt n\)), and false otherwise.
The language of binary palindromes — the set of words \(x \in \{ 0,1\} ^*\) with \(x^{R} = x\) — lies in \(\mathrm{DTIME}(n+1)\): there exist a constant \(c\) and a multi-tape Turing machine over the binary alphabet that, on every input of length \(n\), halts within \(c\, (n+1)\) steps and outputs true exactly when the input is a palindrome, and false otherwise.
The language of binary palindromes — the set of words \(x \in \{ 0,1\} ^*\) equal to their own reversal — belongs to the class \(\mathsf{P}\) of languages decidable by a multi-tape Turing machine in time polynomial in the input length.