Semicomputable function explained

f : Q → R that can be approximated either from above or from below by a computable function.f : Q → R is upper semicomputable, meaning it can be approximated from above, if there exists a computable function \phi(x,k) : Q x N → Q , where x is the desired parameter for f(x) and k is the level of approximation, such that:\lim _{k} \phi(x,k) = f(x) \forall k \in N : \phi(x,k +1 ) \leq \phi(x,k) f : Q → R is lower semicomputable if and only if - f(x) is upper semicomputable or equivalently if there exists a computable function \phi(x,k) such that:\lim _{k} \phi(x,k) = f(x) \forall k \in N : \phi(x,k +1 ) \geq \phi(x,k)

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.