155 Complexity — Time Constructible
155.1 Overview
This module defines time-constructible functions in the sense of Arora–Barak §1.3: a time bound \(T\) is time constructible when \(T(n) \ge n\) and some machine can produce the binary representation of \(T(|x|)\) from any input \(x\) within a constant multiple of \(T(|x|) + 1\) steps. The main result restores the book’s first example under this definition: the identity function is time constructible, witnessed by a four-state machine that maintains a little-endian binary counter on its work tape with an amortized potential argument, then emits the counter as output.
155.2 Declarations
A function \(T : \mathbb {N} \to \mathbb {N}\) is time constructible if \(n \le T(n)\) for every \(n\), and there exist a positive integer constant \(c\) and a finite Turing machine over the binary alphabet that, on every input word \(x \in \{ 0,1\} ^{*}\), computes the binary representation of \(T(|x|)\) (least-significant bit first, with no redundant leading zeros, so \(0\) is represented by the empty word) within at most \(c \cdot (T(|x|) + 1)\) steps.
The successor operation on binary words written least-significant bit first: the empty word maps to the single-bit word \(1\); a word beginning with \(0\) has that bit set to \(1\) and the rest unchanged; a word beginning with \(1\) has that bit cleared to \(0\) and the increment carries recursively into the remaining word.
For a binary word written least-significant bit first, the number of leading \(1\) bits — that is, the number of cells cleared to \(0\) when the word is incremented. A word that is empty or begins with \(0\) has carry length \(0\).
Let \(b\) be a binary word written least-significant bit first, let \(r\) be its carry length (its number of leading \(1\) bits), and let \(w(b)\) denote the number of \(1\) bits in a word. Then the incremented word \(b'\) satisfies \(w(b') + r = w(b) + 1\): each cleared bit lowers the count of ones by one, and the single final write raises it by one.
For every natural number \(n\), applying the word increment to the little-endian binary representation of \(n\) (with no redundant leading zeros; \(0\) is the empty word) yields exactly the binary representation of \(n + 1\), including the case where the word grows by one bit on overflow.
For every binary word \(b\) (least-significant bit first), the incremented word has length at most \(|b| + 1\), and the carry length of \(b\) is at most the length of the incremented word.
Given an input-head displacement \(d \in \{ -1, 0, +1\} \) and the symbol currently scanned on the work tape, the action of one carry step of a one-work-tape binary machine: if the scanned cell holds \(1\), it is overwritten with \(0\), the work head moves right, and the machine continues in its carry state; otherwise (a \(0\) or a blank) the cell is overwritten with \(1\), the work head moves left, and the machine enters its rewind state. In both cases the input head moves by \(d\) and nothing is written to the output.
A finite Turing machine over the binary alphabet with one work tape and four states: count, carry, rewind, and emit. In the count state it performs a carry transition while also advancing the input head, or switches to the emit state when the input is exhausted. In the carry state it propagates an increment along the work tape (clearing \(1\)s rightward until it writes a \(1\) over the first \(0\) or blank). In the rewind state it moves the work head left until it finds the blank at cell \(-1\), then steps right to cell \(0\) and re-enters the count state. In the emit state it copies the work-tape word to the output, one bit per step moving right, and halts at the first blank.
The work-tape contents determined by a finite binary word \(b\): for an integer position \(z\), cell \(z\) holds the \(z\)-th bit of \(b\) when \(0 \le z \lt |b|\), and is blank at every other position (in particular at all negative positions).
The configuration of the one-work-tape four-state counter machine on an input word \(x\) specified by: a state \(q\) among the four counter states, an input-head position \(p\), an integer work-head position \(z\), a finite binary word \(b\) laid out on the nonnegative cells of the work tape (blank elsewhere), and an output word.
Let \(p\) and \(b\) be binary words, and lay the concatenation of \(p\) followed by \(b\) on the nonnegative cells of a tape (blank elsewhere). Then the symbol at cell \(|p|\) is the first bit of \(b\), or blank when \(b\) is empty.
Let \(p\) and \(b\) be binary words, lay their concatenation on the nonnegative cells of a tape, and let \(\beta \) be a bit. Overwriting cell \(|p|\) with \(\beta \) yields exactly the tape of the word obtained by following \(p\) with \(\beta \) and then the tail of \(b\) (all bits of \(b\) after its first). In particular, when \(b\) is empty the stored word is extended by one cell; all other cells, including the negative ones, are unchanged.
Suppose the four-state binary-counter machine is in its carry state with the concatenation of binary words \(p\) and \(b\) on the nonnegative work-tape cells, work head at cell \(|p|\), and empty output. If \(b\) begins with \(1\), one step clears that bit to \(0\) and moves the work head right, staying in the carry state; otherwise one step writes \(1\) at cell \(|p|\) (replacing the first bit of \(b\), or extending the word) and moves the work head left, entering the rewind state. The input head does not move.
Suppose the four-state binary-counter machine is in its carry state with the concatenation of binary words \(p\) and \(b\) on the nonnegative work-tape cells, work head at cell \(|p|\), and empty output, and let \(r\) be the carry length of \(b\) (its number of leading \(1\) bits). Then after exactly \(r + 1\) steps the machine is in the rewind state with the work tape holding \(p\) followed by the incremented word of \(b\), the work head at cell \(|p| + r - 1\), and the input head and output unchanged.
Suppose the four-state binary-counter machine is in its rewind state with a binary word \(b\) on the nonnegative work-tape cells, empty output, and work head at cell \(j - 1\) for some natural number \(j \le |b|\) (so possibly at the blank cell \(-1\)). Then after exactly \(j + 1\) steps the machine is in the count state with the work head at cell \(0\), and the stored word, input-head position, and output all unchanged.
Let \(x\) be an input word and \(i \lt |x|\). Taking one step of the four-state binary-counter machine from the count state — with the input head scanning the \(i\)-th input symbol, the work head at cell \(0\) over a stored binary word \(b\), and empty output — produces the same configuration as taking one step from the carry state with the input head advanced by one position and the same work tape and output.
Let \(x\) be an input word and \(i \lt |x|\). Starting the four-state binary-counter machine in the count state with the input head scanning the \(i\)-th input symbol, a binary word \(b\) stored on the work tape with the work head at cell \(0\), and empty output: after exactly \(2r + 2\) steps, where \(r\) is the carry length of \(b\), the machine is again in the count state with the input head advanced by one position, the work tape holding the incremented word of \(b\), the work head back at cell \(0\), and the output still empty.
Let \(x\) be a binary input word and \(i \le |x|\), and let \(w(i)\) denote the number of \(1\) bits in the binary representation of \(i\). Then there is a step count \(t\) with \(t + 2\, w(i) \le 4i\) such that, after \(t\) steps from its initial configuration on \(x\), the four-state binary-counter machine is in the count state having consumed exactly the first \(i\) input symbols, with the work tape holding the binary representation of \(i\) (least-significant bit first), the work head at cell \(0\), and empty output.
Suppose the four-state binary-counter machine is in its emit state with a binary word \(b\) on the nonnegative work-tape cells, work head at cell \(0\), and empty output. Then for every \(i \le |b|\), after exactly \(i\) steps it is still in the emit state with the work head at cell \(i\), the tape contents and input-head position unchanged, and the output equal to the first \(i\) bits of \(b\).
Suppose the four-state binary-counter machine is in its emit state with a binary word \(b\) on the nonnegative work-tape cells, work head at cell \(0\), and empty output. Then after exactly \(|b| + 1\) steps the machine has halted and its output equals \(b\).
The identity function \(n \mapsto n\) on the natural numbers is time constructible: trivially \(n \le n\) for all \(n\), and there are a positive integer constant \(c\) and a finite Turing machine over the binary alphabet that, on every input word \(x \in \{ 0,1\} ^{*}\), outputs the binary representation of \(|x|\) (least-significant bit first, empty for \(|x| = 0\)) within at most \(c \cdot (|x| + 1)\) steps.