search problem

If $R$ is a binary relation such that $\mathrm{field}(R)\subseteq {\mathrm{\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 of a partial function is a binary relation, and if $T$ calculates a partial function then there is at most one possible output.

A $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 yR(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).

Title	search problem
Canonical name	SearchProblem
Date of creation	2013-03-22 13:01:39
Last modified on	2013-03-22 13:01:39
Owner	Henry (455)
Last modified by	Henry (455)
Numerical id	7
Author	Henry (455)
Entry type	Definition
Classification	msc 68Q25
Defines	calculate