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:
If a partial function is both upper and lower semicomputable it is called computable.
- Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, pp 37–38, Springer, 1997.
|This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.|