Semicomputable function
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.