A log space transducer (LST) is a type of Turing machine used for log-space reductions. A log space transducer, , has three tapes: * A read-only input tape. * A read/write work tape (bounded to at most symbols). * A write-only, write-once output tape. will be designed to compute a log-space computable function (where is the alphabet of both the input and output tapes). 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, . I.E. .