205 Complexity — Transducer
205.1 Overview
A one-pass transducer (a Mealy machine) reads its binary input once from left to right in a finite control state, emitting at most one bit per input bit. This module realizes every such transducer as a Turing machine with no work tapes that runs in time \(|x| + 1\), so its string function is polynomial-time computable. It is the machine-side tool behind several reductions of [AB09, ch. 6], among them stages of the reduction from circuit satisfiability to 3SAT [AB09, Lem. 6.11].
205.2 Declarations
Let \(\sigma \) be a set of control states, let \(\delta : \sigma \times \{ 0,1\} \to \sigma \) be a transition function, and let \(o : \sigma \times \{ 0,1\} \to \{ 0,1\} \cup \{ \bot \} \) be an emission function, where the value \(\bot \) means that nothing is emitted. The string function of the one-pass transducer \((\delta , o)\) started in state \(q \in \sigma \) is the map \(w \mapsto \tau _{\delta ,o}(q, w)\) on \(\{ 0,1\} ^*\) defined recursively by \(\tau _{\delta ,o}(q, \varepsilon ) = \varepsilon \) and
for a bit \(b\) and a string \(w\), where \(\bar o(q,b)\) is the one-bit word \(o(q,b)\) when \(o(q,b) \in \{ 0,1\} \) and the empty word when \(o(q,b) = \bot \).
Let \(\sigma \) be a set of states, \(\delta : \sigma \times \{ 0,1\} \to \sigma \) a transition function and \(o : \sigma \times \{ 0,1\} \to \{ 0,1\} \cup \{ \bot \} \) an emission function, and write \(\tau _{\delta ,o}(q, w)\) for the output of the one-pass transducer that reads \(w\) from left to right starting in state \(q\), where each bit \(b\) read in state \(p\) emits the bit \(o(p,b)\) (or nothing if \(o(p,b) = \bot \)) and moves to state \(\delta (p,b)\). Then for every state \(q\) and all bit strings \(u, v \in \{ 0,1\} ^*\),
where \(\hat\delta (q,u)\) is the state reached from \(q\) by applying \(\delta \) successively to the bits of \(u\) from left to right.
Let \(\sigma \) be a set of states, \(\delta : \sigma \times \{ 0,1\} \to \sigma \) a transition function and \(o : \sigma \times \{ 0,1\} \to \{ 0,1\} \cup \{ \bot \} \) an emission function (\(\bot \) meaning no output). This defines the transition function, for a binary Turing machine with state set \(\sigma \), a read-only input tape, no work tapes and a write-only output tape, given as follows. In state \(q\) reading an input bit \(b\), the machine appends \(o(q,b)\) to the output tape (nothing if \(o(q,b) = \bot \)), moves its input head one cell to the right and enters state \(\delta (q,b)\); in any state, reading a blank input cell, it leaves the head in place, writes nothing and halts.
Let \(\sigma \) be a finite set of states, \(\delta : \sigma \times \{ 0,1\} \to \sigma \) a transition function, \(o : \sigma \times \{ 0,1\} \to \{ 0,1\} \cup \{ \bot \} \) an emission function (\(\bot \) meaning no output) and \(q_0 \in \sigma \) a start state. The transducer machine \(M_{\delta ,o,q_0}\) is the finite binary Turing machine with no work tapes, state set \(\sigma \) and start state \(q_0\) whose transition function, in state \(q\) reading an input bit \(b\), appends \(o(q,b)\) to the output tape (nothing if \(\bot \)), moves the input head one cell right and enters state \(\delta (q,b)\), and on reading a blank input cell halts without moving or writing.
Let \(\sigma \) be a finite set of states, \(\delta : \sigma \times \{ 0,1\} \to \sigma \), \(o : \sigma \times \{ 0,1\} \to \{ 0,1\} \cup \{ \bot \} \) and \(q_0 \in \sigma \), and let \(M\) be the binary Turing machine with no work tapes, state set \(\sigma \) and start state \(q_0\) that, in state \(p\) reading an input bit \(b\), appends \(o(p,b)\) to its output (nothing if \(o(p,b) = \bot \)), moves its input head one cell right and enters \(\delta (p,b)\), and that halts on reading a blank. Let \(x = x_0 x_1 \cdots x_{n-1} \in \{ 0,1\} ^*\), let \(0 \le i \le n\), let \(w = x_i x_{i+1} \cdots x_{n-1}\) be the suffix of \(x\) starting at position \(i\), and let \(C\) be any configuration of \(M\) on input \(x\) that is in state \(q \in \sigma \) with its input head on the cell holding \(x_i\) (on the blank just right of the input when \(i = n\)). Then running \(M\) for \(|w| + 1\) steps from \(C\) reaches the halting state, and the output tape then holds the output of \(C\) followed by \(\tau _{\delta ,o}(q, w)\), where \(\tau _{\delta ,o}(q, w)\) denotes the word emitted by reading \(w\) from left to right starting in state \(q\), each bit \(b\) read in state \(p\) emitting \(o(p,b)\) (or nothing) and moving to \(\delta (p,b)\).
Let \(\sigma \) be a finite set of states, \(\delta : \sigma \times \{ 0,1\} \to \sigma \) a transition function, \(o : \sigma \times \{ 0,1\} \to \{ 0,1\} \cup \{ \bot \} \) an emission function (\(\bot \) meaning no output) and \(q_0 \in \sigma \), and let \(M\) be the binary Turing machine with no work tapes, state set \(\sigma \) and start state \(q_0\) that, in state \(p\) reading an input bit \(b\), appends \(o(p,b)\) to its output (nothing if \(\bot \)), moves its input head right and enters \(\delta (p,b)\), and halts on reading a blank. Then \(M\) computes the function \(x \mapsto \tau _{\delta ,o}(q_0, x)\) in time \(n + 1\): on every input \(x \in \{ 0,1\} ^*\) it halts within \(|x| + 1\) steps with \(\tau _{\delta ,o}(q_0, x)\) on its output tape, where \(\tau _{\delta ,o}(q_0, x)\) is the word emitted by reading \(x\) from left to right starting in \(q_0\), each bit \(b\) read in state \(p\) emitting \(o(p,b)\) (or nothing) and moving to \(\delta (p,b)\).
Let \(\sigma \) be a finite set of states, \(\delta : \sigma \times \{ 0,1\} \to \sigma \) a transition function, \(o : \sigma \times \{ 0,1\} \to \{ 0,1\} \cup \{ \bot \} \) an emission function (\(\bot \) meaning no output) and \(q_0 \in \sigma \), and let \(\tau _{\delta ,o}(q_0, x)\) be the word emitted by the one-pass transducer reading \(x \in \{ 0,1\} ^*\) from left to right starting in \(q_0\), where each bit \(b\) read in state \(p\) emits \(o(p,b)\) (or nothing) and moves to \(\delta (p,b)\). Then the map \(x \mapsto \tau _{\delta ,o}(q_0, x)\) is polynomial-time computable: some finite binary Turing machine computes it within \(C(n+1)^c\) steps on every input of length \(n\), for some constants \(C, c \in \mathbb {N}\).