Editing Log-space reduction (section)

=== Closure ===
The most important property of logspace computability is that, if functions <math>f, g</math> are logspace computable, then so is their [[Function composition|composition]] <math>g \circ f</math>. This allows the concept of logspace reduction to be transitive.

Given two logspace transducers, their composition is still a logspace transducer: feed the output from one transducer (A→B) to another (B→C). At first glance, this seems incorrect because intuitively, the A→C transducer needs to store the output tape from the A→B transducer onto the work tape, in order to feed it into the B→C reducer, but this is not necessary, by the following construction.

Define the A→C transducer as follows: It simulates the operations of B→C transducer. Every time the B→C transducer needs to make a read, the A→C transducer re-run the A→B transducer to re-compute only the exact output bit that is needed, and so only one bit of the output of the A→B transducer needs to be stored at any moment.