In computational complexity theory, a log space transducer (LST) is a type of Turing machine used for log-space reductions.
is the alphabet of both the input and output tapes).
on its input tape, when the machine halts, it will have
remaining on its output tape.
if there exists a log-space computable function
that will convert an input from problem
This seems like a rather convoluted idea, but it has two useful properties that are desirable for a reduction: Transitivity holds because it is possible to feed the output tape of one reducer (A→B) to another (B→C).
At first glance, this seems incorrect because the A→C reducer needs to store the output tape from the A→B reducer onto the work tape in order to feed it into the B→C reducer, but this is not true.
This theoretical computer science–related article is a stub.