Log-space transducer


A log space transducer is a type of Turing machine used for log-space reductions.
A log space transducer,, has three tapes:
will be designed to compute a log-space computable function . If is executed with on its input tape, when the machine halts, it will have remaining on its output tape.
A language is said to be log-space reducible to a language if there exists a log-space computable function,, which will convert an input from problem into an input to problem. I.E..
This seems like a rather convoluted idea, but it has two useful properties that are desirable for a reduction:
  1. The property of transitivity holds..
  2. If A reduces to B, and B is in L, then we know A is in L.
Transitivity holds because it is possible to feed the output tape of one reducer to another. 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. Each time the B→C reducer needs to access its input tape, the A→C reducer can re-run the A→B reducer, and so the output of the A→B reducer never needs to be stored entirely at once.