In computability theory, a semicomputable function is a partial function f : Q → R {\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} } that can be approximated either from above or from below by a computable function. More precisely a partial function f : Q → R {\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} } is upper semicomputable, meaning it can be approximated from above, if there exists a computable function ϕ ( x , k ) : Q × N → Q {\displaystyle \phi (x,k):\mathbb {Q} \times \mathbb {N} \rightarrow \mathbb {Q} } , where x {\displaystyle x} is the desired parameter for f ( x ) {\displaystyle f(x)} and k {\displaystyle k} is the level of approximation, such that:
lim k → ∞ ϕ ( x , k ) = f ( x ) {\displaystyle \lim _{k\rightarrow \infty }\phi (x,k)=f(x)}
∀ k ∈ N : ϕ ( x , k + 1 ) ≤ ϕ ( x , k ) {\displaystyle \forall k\in \mathbb {N} :\phi (x,k+1)\leq \phi (x,k)}
Completely analogous a partial function f : Q → R {\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} } is lower semicomputable if and only if − f ( x ) {\displaystyle -f(x)} is upper semicomputable or equivalently if there exists a computable function ϕ ( x , k ) {\displaystyle \phi (x,k)} such that:
lim k → ∞ ϕ ( x , k ) = f ( x ) {\displaystyle \lim _{k\rightarrow \infty }\phi (x,k)=f(x)}
∀ k ∈ N : ϕ ( x , k + 1 ) ≥ ϕ ( x , k ) {\displaystyle \forall k\in \mathbb {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.