1 Answers
In computational complexity theory, a log space transducer is a type of Turing machine used for log-space reductions.
A log space transducer, M {\displaystyle M} , has three tapes:
M {\displaystyle M} will be designed to compute a log-space computable function f : Σ ∗ → Σ ∗ {\displaystyle f\colon \Sigma ^{\ast }\rightarrow \Sigma ^{\ast }} . If M {\displaystyle M} is executed with w {\displaystyle w} on its input tape, when the machine halts, it will have f {\displaystyle f} remaining on its output tape.
A language A ⊆ Σ ∗ {\displaystyle A\subseteq \Sigma ^{\ast }} is said to be log-space reducible to a language B ⊆ Σ ∗ {\displaystyle B\subseteq \Sigma ^{\ast }} if there exists a log-space computable function f {\displaystyle f} that will convert an input from problem A {\displaystyle A} into an input to problem B {\displaystyle B} in such a way that w ∈ A ⟺ f ∈ B {\displaystyle w\in A\iff f\in B}.