SearchProblem 2002-09-06 11:51:19 2004-04-11 22:10:52 Definition calculate % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here %\PMlinkescapeword{theory} If $R$ is a binary relation such that $\operatorname{field}(R)\subseteq\Gamma^+$ and $T$ is a Turing machine, then $T$ \emph{calculates} $f$ if: \begin{itemize} \item If $x$ is such that there is some $y$ such that $R(x,y)$ then $T$ accepts $x$ with output $z$ such that $R(x,z)$ (there may be multiple $y$, and $T$ need only find one of them) \item If $x$ is such that there is no $y$ such that $R(x,y)$ then $T$ rejects $x$ \end{itemize} Note that the \PMlinkescapetext{graph} of a partial function is a binary relation, and if $T$ calculates a partial function then there is at most one possible output. A \PMlinkescapetext{relation} $R$ can be viewed as a \emph{search problem}, and a Turing machine which calculates $R$ is also said to solve it. Every search problem has a corresponding decision problem, namely $L(R)=\{x\mid \exists y R(x,y)\}$. This definition may be generalized to $n$-ary relations using any suitable encoding which allows multiple strings to be compressed into one string (for instance by listing them consecutively with a delimiter).