Logspace transducer

A deterministic Turing machine with read-only input, $O(\log (n+2))$ work space, and successive write-only output whose contents it cannot inspect. A transducer for a total function halts on every input. It has a polynomial number of internal Turing machine configurations, so a halting run emits only a polynomial number of symbols. The unreadable output position does not affect subsequent transitions.

A total function computed by a halting logspace transducer. Its output may be much longer than its work tapes. Logspace-computable functions compose using logspace composition by recomputation.

To simulate $g$ on the virtual input $f(x)$, store the simulated input-head position and rerun the logspace transducer for $f$ whenever an input symbol is requested. Count emitted symbols until the requested position is reached. The intermediate output has polynomial length, so its positions take $O(\log n)$ bits, and the work space of $g$ is also $O(\log n)$. Storage used by successive recomputations is reused. This proves closure of logspace-computable functions under composition and transitivity of logspace many-one reductions.