Editing Search problem (section)

==Definition==
[[PlanetMath]] defines the problem as follows:<ref>{{cite web |title=PlanetMath |url=https://planetmath.org/searchproblem |website=planetmath.org |access-date=15 May 2025}}{{Creative Commons text attribution notice|cc=by2.5|from this source=yes}}</ref>

If <math>R</math> is a binary relation such that <math>\operatorname{field}(R)\subseteq\Gamma^{+}</math> and <math>T</math> is a [[Turing machine]], then <math>T</math> calculates <math>f</math> if:<ref group="note" name="def-henry-405"/>

* If <math>x</math> is such that there is some <math>y</math> such that <math>R(x,y)</math> then <math>T</math> accepts <math>x</math> with output <math>z</math> such that <math>R(x,z)</math>. (there may be multiple <math>y</math>, and <math>T</math> need only find one of them)
* If <math>x</math> is such that there is no <math>y</math> such that <math>R(x,y)</math> then <math>T</math> rejects <math>x</math>.

:Note that the graph of a [[partial function]] is a binary relation, and if <math>T</math> calculates a partial function then there is at most one possible output.

:A <math>R</math> can be viewed as a ''search problem'', and a Turing machine which calculates <math>R</math> is also said to solve it. Every search problem has a corresponding [[decision problem]], namely <math>L(R)=\{x\mid \exists y R(x,y)\}.</math>

:This definition can be generalized to ''n''-ary relations by any suitable encoding which allows multiple strings to be compressed into one string (for instance by listing them consecutively with a [[delimiter]]).