If is such that there is some such that then accepts with output such that (there may be multiple , and need only find one of them)
If is such that there is no such that then rejects
Note that the of a partial function is a binary relation, and if calculates a partial function then there is at most one possible output.
A can be viewed as a search problem, and a Turing machine which calculates is also said to solve it. Every search problem has a corresponding decision problem, namely .
This definition may be generalized to -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).
|Date of creation||2013-03-22 13:01:39|
|Last modified on||2013-03-22 13:01:39|
|Last modified by||Henry (455)|