Semicomputable function

In computability theory, a semicomputable function is a partial function  f : \mathbb{Q} \rightarrow \mathbb{R} that can be approximated either from above or from below by a computable function.

More precisely a partial function  f : \mathbb{Q} \rightarrow \mathbb{R} is upper semicomputable, meaning it can be approximated from above, if there exists a computable function  \phi(x,k) : \mathbb{Q} \times \mathbb{N} \rightarrow \mathbb{Q}, where x is the desired parameter for  f(x) and  k is the level of approximation, such that:

Completely analogous a partial function  f : \mathbb{Q} \rightarrow \mathbb{R} is lower semicomputable iff  -f(x) is upper semicomputable or equivalently if there exists a computable function  \phi(x,k) such that

If a partial function is both upper and lower semicomputable it is called computable.

See also

References

This article is issued from Wikipedia - version of the Saturday, December 10, 2011. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.