Log-space transducer
In computational complexity theory, a log space transducer (LST) is a type of Turing machine used for log-space reductions. A log space transducer, [math]\displaystyle{ M }[/math], has three tapes:
- A read-only input tape.
- A read/write work tape (bounded to at most [math]\displaystyle{ O(\log n) }[/math] symbols).
- A write-only, write-once output tape.
[math]\displaystyle{ M }[/math] will be designed to compute a log-space computable function [math]\displaystyle{ f\colon \Sigma^\ast \rightarrow \Sigma^\ast }[/math] (where [math]\displaystyle{ \Sigma }[/math] is the alphabet of both the input and output tapes). If [math]\displaystyle{ M }[/math] is executed with [math]\displaystyle{ w }[/math] on its input tape, when the machine halts, it will have [math]\displaystyle{ f(w) }[/math] remaining on its output tape.
A language [math]\displaystyle{ A \subseteq \Sigma^\ast }[/math] is said to be log-space reducible to a language [math]\displaystyle{ B \subseteq \Sigma^\ast }[/math] if there exists a log-space computable function [math]\displaystyle{ f }[/math] that will convert an input from problem [math]\displaystyle{ A }[/math] into an input to problem [math]\displaystyle{ B }[/math] in such a way that [math]\displaystyle{ w \in A \iff f(w) \in B }[/math].
This seems like a rather convoluted idea, but it has two useful properties that are desirable for a reduction:
- The property of transitivity holds. (A reduces to B and B reduces to C implies A reduces to C).
- 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 (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. 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.
References
- Szepietowski, Andrzej (1994), Turing Machines with Sublogarithmic Space , Springer Press, ISBN:3-540-58355-6. Retrieved on 2008-12-03.
- Sipser, Michael (2012), Introduction to the Theory of Computation, Cengage Learning, ISBN:978-0-619-21764-8.
 |  |
