Semicomputable function
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.
- v
- t
- e