Semicomputable function

In computability theory, a semicomputable function is a partial function [math]\displaystyle{ f : \mathbb{Q} \rightarrow \mathbb{R} }[/math] that can be approximated either from above or from below by a computable function. More precisely a partial function [math]\displaystyle{ f : \mathbb{Q} \rightarrow \mathbb{R} }[/math] is upper semicomputable, meaning it can be approximated from above, if there exists a computable function [math]\displaystyle{ \phi(x,k) : \mathbb{Q} \times \mathbb{N} \rightarrow \mathbb{Q} }[/math], where [math]\displaystyle{ x }[/math] is the desired parameter for [math]\displaystyle{ f(x) }[/math] and [math]\displaystyle{ k }[/math] is the level of approximation, such that:

• [math]\displaystyle{ \lim_{k \rightarrow \infty} \phi(x,k) = f(x) }[/math]
• [math]\displaystyle{ \forall k \in \mathbb{N} : \phi(x,k+1) \leq \phi(x,k) }[/math]

Completely analogous a partial function [math]\displaystyle{ f : \mathbb{Q} \rightarrow \mathbb{R} }[/math] is lower semicomputable if and only if [math]\displaystyle{ -f(x) }[/math] is upper semicomputable or equivalently if there exists a computable function [math]\displaystyle{ \phi(x,k) }[/math] such that:

• [math]\displaystyle{ \lim_{k \rightarrow \infty} \phi(x,k) = f(x) }[/math]
• [math]\displaystyle{ \forall k \in \mathbb{N} : \phi(x,k+1) \geq \phi(x,k) }[/math]

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.