If $R$ is a binary relation such that $\operatorname{field}(R)\subseteq\Gamma^+$ and $T$ is a Turing machine, then $T$ calculates $f$ if:

• 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)
• If $x$ is such that there is no $y$ such that $R(x,y)$ then $T$ rejects $x$

Note that the 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 relation $R$ can be viewed as a 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).