In computability theory, a '''semicomputable function''' is a partial function <math> 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> f : \mathbb{Q} \rightarrow \mathbb{R} </math> is '''upper semicomputable''', meaning it can be approximated from above, if there exists a computable function <math> \phi(x,k) : \mathbb{Q} \times \mathbb{N} \rightarrow \mathbb{Q}</math>, where <math>x</math> is the desired parameter for <math> f(x) </math> and <math> k </math> is the level of approximation, such that:
* <math> \lim_{k \rightarrow \infty} \phi(x,k) = f(x) </math> * <math> \forall k \in \mathbb{N} : \phi(x,k+1) \leq \phi(x,k) </math>
Completely analogous a partial function <math> f : \mathbb{Q} \rightarrow \mathbb{R} </math> is '''lower semicomputable''' if and only if <math> -f(x) </math> is upper semicomputable or equivalently if there exists a computable function <math> \phi(x,k) </math> such that:
* <math> \lim_{k \rightarrow \infty} \phi(x,k) = f(x) </math> * <math> \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.
{{DEFAULTSORT:Semicomputable Function}} Category:Mathematical logic {{mathlogic-stub}}