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:
![{\displaystyle \lim _{k\rightarrow \infty }\phi (x,k)=f(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b1034112ec02eb077123147424e5e6a1ad7dec6)
![{\displaystyle \forall k\in \mathbb {N} :\phi (x,k+1)\leq \phi (x,k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2821d02fcf84ac93bda72c400c1c27bac7fd1f1f)
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:
![{\displaystyle \lim _{k\rightarrow \infty }\phi (x,k)=f(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b1034112ec02eb077123147424e5e6a1ad7dec6)
![{\displaystyle \forall k\in \mathbb {N} :\phi (x,k+1)\geq \phi (x,k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/387634d4f079c64f6a520fd6f1d53ed498c7be26)
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.