[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 is a member of sigma* if

q0x move zero or more times to qfy

where qf is a final state. (Actually, this definition is a bit stronger than necessary; can you see how?)

Important!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