In other words, a Turing machine defines a function y=f(x) for strings x, y * if

where q_{f} 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