a transducer

So far a Turing machine has been a judge, answering yes or no. But a machine can also be a calculator: take some input and produce some output. A transducer is a Turing machine used this way, to compute a FUNCTION rather than to decide membership. Instead of asking 'is this string in the language?', you ask 'what does this string turn into?'. Think of a vending machine that, fed coins, returns a specific snack, not merely a yes-or-no.

Concretely, a transducer starts with the input written on its tape, runs, and when it halts, whatever is left written on the tape (read off by a fixed convention, for example the non-blank string starting where the head ends) is the output. We say the machine computes a function f if, started on any input w, it halts with f(w) on the tape. For this to define a genuine function the machine must halt on every input, just like a decider, so the output is always defined. A simple example: a transducer that reads a binary number and writes back that number plus one (binary increment), or one that copies its input to produce ww.

Transducers matter because they show the Turing machine is a model of computation in the full sense, not just an acceptor of languages. Every notion of a computable function (adding numbers, sorting a list, compiling a program) can be cast as a transducer. In fact deciding a language is a special case: a decider is a transducer whose output is just one of two values, accept or reject. The Church-Turing thesis, that the computable functions are exactly the Turing-computable ones, is really a statement about what transducers can do.