Turing computableTuringComputable2002-03-23 01:57:492006-01-15 23:05:33Definition\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
%\usepackage{psfrag}
%\usepackage{graphicx}
%\usepackage{xypic}A function is \emph{Turing computable} if the function's value can be
computed with a Turing machine.
More specifically, let $D$ be a set of words in a given alphabet and
let $f$ be a function which maps elements of $D$ to words on the
same alphabet. We say that $f$ is \emph{Turing computable} if there
exists a Turing machine such that
\begin{itemize}
\item If one starts the Turing machine with a word $w \in D$ as the
initial content of the tape, the computation will halt.
\item When the computation halts, the tape will read $f(w)$.
\end{itemize}
Because of the fact that all types of Turing machines (deterministic,
non-deterministic, single head, multiple head, etc.) all have the same
computational power, it does not matter which type of Turing machine
one uses in the definition.
It is not hard to find examples of Turing computable functions ---
because Turing machines provide an idealized model for the operation
of the digital computer, any function which can be evaluated by a
computer provides an example.