Semicomputable function

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

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

$lim_{k \to \infty} ϕ (x, k) = f (x)$
$\forall k \in ℕ : ϕ (x, k + 1) \leq ϕ (x, k)$

Completely analogous a partial function $f : ℚ \to ℝ$ is lower semicomputable if and only if $- f (x)$ is upper semicomputable or equivalently if there exists a computable function $ϕ (x, k)$ such that:

$lim_{k \to \infty} ϕ (x, k) = f (x)$
$\forall k \in ℕ : ϕ (x, k + 1) \geq ϕ (x, k)$

If a partial function is both upper and lower semicomputable it is called computable.

References

Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, pp 37–38, Springer, 1997.

This mathematical logic–related article is a stub. You can help Wikipedia by adding missing information.

Semicomputable function

See also

References