In computability theory, a semicomputable function is a partial function that can be approximated either from above or from below by a computable function.
More precisely a partial function is upper semicomputable, meaning it can be approximated from above, if there exists a computable function , where is the desired parameter for and is the level of approximation, such that:
Completely analogous a partial function is lower semicomputable if and only if is upper semicomputable or equivalently if there exists a computable function such that:
If a partial function is both upper and lower semicomputable it is called computable.
See also Computability theory
References
Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, pp 37–38, Springer, 1997.