Semicomputable Function

In computability theory, a semicomputable function is a partial function $f : \mathbb \rightarrow \mathbb$ that can be approximated either from above or from below by a computable function.

More precisely a partial function $f : \mathbb \rightarrow \mathbb$ is upper semicomputable, meaning it can be approximated from above, if there exists a computable function $\phi(x,k) : \mathbb \times \mathbb \rightarrow \mathbb$, where $x$ is the desired parameter for $f(x)$ and $k$ is the level of approximation, such that:

* $\lim_ \phi(x,k) = f(x)$
* $\forall k \in \mathbb : \phi(x,k+1) \leq \phi(x,k)$

Completely analogous a partial function $f : \mathbb \rightarrow \mathbb$ 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_ \phi(x,k) = f(x)$
* $\forall k \in \mathbb : \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.

Mathematical logic
{{mathlogic-stub