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://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO8QoDiQaNwPatdBoNmOnqeQzNKPaDaPzjK0aDvBzqs2othFnjJCnqa2)
![{\displaystyle \forall k\in \mathbb {N} :\phi (x,k+1)\leq \phi (x,k)}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO8OyjePnjmOnAzAyjvFoNCNoAvFzNdDzjmQoNhDaDJEoqa3nAwPnDhA)
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://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO8QoDiQaNwPatdBoNmOnqeQzNKPaDaPzjK0aDvBzqs2othFnjJCnqa2)
![{\displaystyle \forall k\in \mathbb {N} :\phi (x,k+1)\geq \phi (x,k)}](https://amansaja.com/index.php?q=Mfv0Kfa6bO93MqTXLqrCMqiSL3dZb2hQMu9Onpz0p3oPb21BngBFb21FJgGRKArSngrOb3z2nO8NyjK2aNvCzgoQzNBDzDvAzAi1aDlAnjnAaqw1a2rCzjC4oNJEnte2)
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.