Semicomputable function

In computability theory, a semicomputable function is a partial function $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 : \mathbb{Q} \rightarrow \mathbb{R}$ is upper semicomputable, meaning it can be approximated from above, if there exists a computable function $\phi(x,k) : \mathbb{Q} \times \mathbb{N} \rightarrow \mathbb{Q}$ , where $x$ is the desired parameter for $f(x)$ and $k$ is the level of approximation, such that:

$\lim_{k \rightarrow \infty} \phi(x,k) = f(x)$
$\forall k \in \mathbb{N} : \phi(x,k+1) \leq \phi(x,k)$

Completely analogous a partial function $f : \mathbb{Q} \rightarrow \mathbb{R}$ is lower semicomputable iff $-f(x)$ is upper semicomputable or equivalently if there exists a computable function $\phi(x,k)$ such that

$\lim_{k \rightarrow \infty} \phi(x,k) = f(x)$
$\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.

References

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

This article is issued from Wikipedia - version of the 12/10/2011. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Semicomputable function

See also

References