[Overview] [Previous] [Next]
Turing Machines as Transducers
A Turing machine can be used as a transducer.
The most obvious way to do this is to treat the entire
nonblank portion of the initial tape as input,
and to treat the entire nonblank portion of the
tape when the machine halts as output.
In other words, a Turing machine defines a function y=f(x) for strings x,
y 
*
if
q0x 
qfy
where qf is a final state.
(Actually, this definition is a bit stronger than necessary;
can you see how?)
A
function f is Turing computable if there exists a Turing machine that
can perform the above task.
Copyright © 1996 by David Matuszek
Last modified Mar 25, 1996