Back to the index. Or to the chambers

This article has 6 links. View as Cloud or List.

General Associativity Relation Language Relation Theory Turing Machine Decides

1	Relation
1	Relation Theory
1	Language
1	General Associativity
3	Decides
3	Turing Machine

Loading ...

Planetmath Browser (2008—2009)

BSD licence | A django site

All articles taken from PlanetMath.org snapshot under CC-BY-SA licence.

→ The original article on PlanetMath.org

Other Formats: LaTeX

New! You can click on formulas to copy the LaTeX source to your clipboard. | Math Videos

Search Problem

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

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 graph of a partial function is a binary relation, and if calculates a partial function then there is at most one possible output.

A relation 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 $L(R)=\{x\mid \exists y R(x,y)\}$ .

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).