157 Complexity — Composition
157.1 Overview
This module provides the basic computability combinators for bundled multi-tape Turing machines over the Boolean alphabet: the identity function, every constant function, and equality testing against a fixed word are computable in linear time, and time-bounded computability is closed under sequential composition. It also provides two untimed guarded combinators: sequential composition of two arbitrary machines at the level of their halting relations, and branching between two machines according to a predicate decided by a third machine.
157.2 Declarations
The machine over the Boolean alphabet with no work tapes and a single state that copies its input to its output: on scanning an input symbol it appends that symbol to the output and moves the input head one cell right, and on scanning a boundary blank it halts.
Let \(x\) be a Boolean word and run the one-state copy machine from its initial configuration on input \(x\). For every \(t \le \left\lvert x\right\rvert \), after \(t\) steps the machine is still live in its unique state, its input head sits at position \(t + 1\) (in the convention where position \(0\) is the left boundary blank and position \(j\) with \(1 \le j \le \left\lvert x\right\rvert \) scans the \(j\)-th input symbol), and its output is exactly the first \(t\) symbols of \(x\).
There exist a multi-tape Turing machine \(M\) over the Boolean alphabet and a constant \(c\) such that \(M\) computes the identity function on Boolean words in time \(c \cdot (n + 1)\): on every input \(x\), within \(c \cdot (\left\lvert x\right\rvert + 1)\) steps \(M\) halts with output exactly \(x\).
For a fixed Boolean word \(w\), the machine over the Boolean alphabet with no work tapes whose states are \(\{ 0, \dots , \left\lvert w\right\rvert \} \), forming the emission chain for \(w\): state \(i \lt \left\lvert w\right\rvert \), regardless of the symbols scanned, appends the \(i\)-th symbol of \(w\) (zero-indexed) to the output and passes to state \(i + 1\), and state \(\left\lvert w\right\rvert \) halts.
For every fixed Boolean word \(w\) there exist a multi-tape Turing machine \(M\) over the Boolean alphabet and a constant \(c\) such that \(M\) computes the constant function \(x \mapsto w\) in time \(c \cdot (n + 1)\): on every input \(x\), within \(c \cdot (\left\lvert x\right\rvert + 1)\) steps \(M\) halts with output exactly \(w\).
For fixed Boolean words \(w_0\), \(u\), \(v\), the machine over the Boolean alphabet with no work tapes whose states are \(\left\lvert w_0\right\rvert + 1\) comparison states together with an emission chain for \(u\) and an emission chain for \(v\). Comparison state \(i \lt \left\lvert w_0\right\rvert \) moves the input head right and passes to comparison state \(i + 1\) when the scanned symbol is the \(i\)-th symbol of \(w_0\), and enters the emission chain for \(v\) otherwise; comparison state \(\left\lvert w_0\right\rvert \) enters the chain for \(u\) on a boundary blank and the chain for \(v\) on any remaining symbol. Each emission chain writes its word one symbol per step and halts.
Fix Boolean words \(w_0\), \(u\), \(v\), an input word \(x\), and a Boolean \(b\), and write \(z\) for the word \(u\) if \(b\) is true and \(v\) if \(b\) is false. Let \(c\) be any configuration of the fixed-word comparator machine for \(w_0\), \(u\), \(v\) on input \(x\) whose state is the initial state of the emission chain for \(z\) and whose output is still empty. Then after exactly \(\left\lvert z\right\rvert + 1\) further steps the machine has halted with output exactly \(z\), independently of the position of the input head in \(c\).
Fix Boolean words \(w_0\), \(u\), \(v\) and an input word \(x\), and let \(i\) and \(r\) be natural numbers with \(\left\lvert w_0\right\rvert = i + r\), \(i \le \left\lvert x\right\rvert \), and the first \(i\) symbols of \(x\) equal to the first \(i\) symbols of \(w_0\). From any configuration of the fixed-word comparator machine for \(w_0\), \(u\), \(v\) on input \(x\) that is in comparison state \(i\) with its input head at position \(i + 1\) (position \(0\) being the left boundary blank) and with empty output, there is a \(t \le r + \max (\left\lvert u\right\rvert , \left\lvert v\right\rvert ) + 2\) such that after \(t\) steps the machine has halted, with output \(u\) if \(x = w_0\) and output \(v\) otherwise.
For all fixed Boolean words \(w_0\), \(u\), \(v\) there exist a multi-tape Turing machine \(M\) over the Boolean alphabet and a constant \(c\) such that \(M\) computes in time \(c \cdot (n + 1)\) the function sending a Boolean word \(w\) to \(u\) when \(w = w_0\) and to \(v\) otherwise.
Let \(M_1\) and \(M_2\) be multi-tape Turing machines over the Boolean alphabet, let \(f\) and \(g\) be functions on Boolean words, and let \(T_1, T_2 : \mathbb {N} \to \mathbb {N}\) with \(T_2\) monotone. Suppose \(M_1\) computes \(f\) in time \(T_1\) and \(M_2\) computes \(g\) in time \(T_2\), meaning that on every input \(x\) the machine halts within \(T_i(\left\lvert x\right\rvert )\) steps with the function value on its output tape. Then there exist a machine \(M\) and a constant \(c\) such that \(M\) computes the composite \(g \circ f\) in time \(n \mapsto c \cdot \bigl(T_1(n) + T_2(T_1(n)) + 1\bigr)\).
For any two multi-tape Turing machines \(M_1\) and \(M_2\) over the Boolean alphabet — with no totality or time hypotheses — there exists a machine \(M\) such that for all Boolean words \(x\) and \(w\): \(M\) halts on input \(x\) with output \(w\) (within some number of steps) if and only if there is a Boolean word \(y\) such that \(M_1\) halts on input \(x\) with output \(y\) and \(M_2\) halts on input \(y\) with output \(w\). In particular, if \(M_1\) diverges on \(x\), or halts but \(M_2\) diverges on its output, then \(M\) diverges on \(x\).
Given three machines \(D\), \(M_1\), \(M_2\) over the Boolean alphabet with \(k_D\), \(k_1\), \(k_2\) work tapes respectively, the machine with \(k_D + k_1 + k_2\) work tapes whose finite control simulates \(D\) on the first tape block with \(D\)’s emissions suppressed and the first emitted symbol captured in a state register. After the simulated \(D\) halts, a control phase rewinds the input head to its initial position and then transfers control to a disjoint copy of the branch union of \(M_1\) and \(M_2\) selected by the register bit, running on the fresh remaining tape blocks; when the register is empty at dispatch the machine halts.
Given machines \(D\), \(M_1\), \(M_2\) over the Boolean alphabet and a configuration \(c\) of \(D\) on an input \(x\), the configuration of the conditional-dispatch machine for \(D\), \(M_1\), \(M_2\) on \(x\) whose control state pairs the state of \(c\) with the first symbol (if any) of \(c\)’s output stored in the register, whose input head agrees with that of \(c\), whose first tape block carries \(c\)’s work tapes while all branch tapes are blank with heads at the origin, and whose real output is empty.
Let \(D\), \(M_1\), \(M_2\) be machines over the Boolean alphabet and let \(c\) be a configuration of \(D\) on an input \(x\) whose state is not the halting state. Then one step of the conditional-dispatch machine from the embedded controller configuration of \(c\) equals the embedded controller configuration of one step of \(D\) from \(c\); in particular the register tracks the first symbol of the simulated output, with no hypothesis on \(c\)’s output.
Let \(D\), \(M_1\), \(M_2\) be machines over the Boolean alphabet, let \(c\) be a configuration of \(D\) on an input \(x\), and let \(t\) be a number of steps such that the run of \(D\) from \(c\) has not halted at any time \(s \lt t\). Then the \(t\)-step run of the conditional-dispatch machine from the embedded controller configuration of \(c\) equals the embedded controller configuration of the \(t\)-step run of \(D\) from \(c\).
Let \(D\), \(M_1\), \(M_2\) be machines over the Boolean alphabet, let \(x\) be a Boolean word, and let \(b\) be a Boolean such that \(D\) halts on input \(x\) with the singleton output consisting of \(b\) alone (within some number of steps). Then there exist a time \(t\) and residual contents and head positions for the controller’s tape block such that the \(t\)-step run of the conditional-dispatch machine from its initial configuration on \(x\) is exactly the right-block embedding of the initial configuration on \(x\) of the branch machine selected by \(b\) (the branch union of \(M_1\) and \(M_2\)), alongside those residual controller tapes.
Let \(D\), \(M_1\), \(M_2\) be multi-tape Turing machines over the Boolean alphabet and let \(p\) be a Boolean-valued predicate on Boolean words such that \(D\) computes the function \(x \mapsto [p(x)]\): on every input \(x\) it eventually halts with the single symbol \(p(x)\) as its output. Then there exists a machine \(M\) such that for all Boolean words \(x\) and \(w\): \(M\) halts on input \(x\) with output \(w\) (within some number of steps) if and only if the branch machine selected by \(p(x)\) — namely \(M_1\) when \(p(x)\) is true and \(M_2\) when \(p(x)\) is false — halts on that same input \(x\) with output \(w\) (within some number of steps).
157.3 Additional declarations
Let \(M_1\) and \(M_2\) be multi-tape Turing machines over the Boolean alphabet, let \(x\), \(y\), \(o\) be Boolean words, and let \(t_1, t_2 \in \mathbb {N}\). Consider the buffered sequential composition machine of \(M_1\) and \(M_2\), which simulates \(M_1\) on its input with \(M_1\)’s output diverted to a buffer work tape, rewinds the buffer, and then simulates \(M_2\) reading the buffer as its input. If \(M_1\) halts on input \(x\) within \(t_1\) steps with output \(y\), and \(M_2\) halts on input \(y\) within \(t_2\) steps with output \(o\), then this composition machine halts on input \(x\) within \(t_1 + \left\lvert y\right\rvert + 2 + t_2\) steps with output \(o\). Neither machine is required to halt on any other input.
Let \(M\) and \(U\) be multi-tape Turing machines over the Boolean alphabet, let \(f\) and \(g\) be functions on Boolean words, and let \(T_1, T_2 : \mathbb {N} \to \mathbb {N}\) be arbitrary. Suppose \(M\) computes \(f\) in time \(T_1\), meaning that on every input \(x\) it halts within \(T_1(\left\lvert x\right\rvert )\) steps with output \(f(x)\), and suppose that for every Boolean word \(x\) the machine \(U\) on input \(f(x)\) halts within \(T_2(\left\lvert x\right\rvert )\) steps with output \(g(x)\), the budget being measured at the length of the original word \(x\). Then there is a machine \(N\) over the Boolean alphabet that computes \(g\) in time \(n \mapsto 2\, T_1(n) + T_2(n) + 2\); no monotonicity of \(T_2\) is required, and \(U\) need not halt on words outside the image of \(f\).