In computability theory, a semicomputable function is a partial function f : Q → R that can be approximated either from above or from below by a computable function.
More precisely a partial function f : Q → R is upper semicomputable, meaning it can be approximated from above, if there exists a computable function ϕ ( x , k ) : Q × N → Q , where x is the desired parameter for f ( x ) and k is the level of approximation, such that:
lim k → ∞ ϕ ( x , k ) = f ( x ) ∀ k ∈ N : ϕ ( x , k + 1 ) ≤ ϕ ( x , k ) Completely analogous a partial function f : Q → R is lower semicomputable iff − f ( x ) is upper semicomputable or equivalently if there exists a computable function ϕ ( x , k ) such that
lim k → ∞ ϕ ( x , k ) = f ( x ) ∀ k ∈ N : ϕ ( x , k + 1 ) ≥ ϕ ( x , k ) If a partial function is both upper and lower semicomputable it is called computable.
