# Semicomputable function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Semicomputable_function
> Markdown URL: https://mediated.wiki/source/Semicomputable_function.md
> Source: https://en.wikipedia.org/wiki/Semicomputable_function
> Source revision: 1032157670
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [computability theory](/source/recursion_theory), a '''semicomputable function''' is a [partial function](/source/partial_function) <math> f : \mathbb{Q} \rightarrow \mathbb{R} </math> that can be approximated either from above or from below by a [computable function](/source/computable_function).

More precisely a [partial function](/source/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](/source/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](/source/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](/source/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](/source/partial_function) is both upper and lower '''semicomputable''' it is called computable.

==See also==
* [Computability theory](/source/recursion_theory)

== References ==

* Ming Li and Paul Vitányi, ''An Introduction to Kolmogorov Complexity and Its Applications'', pp 37&ndash;38, Springer, 1997.

{{DEFAULTSORT:Semicomputable Function}}
Category:Mathematical logic
{{mathlogic-stub}}

---
Adapted from the Wikipedia article [Semicomputable function](https://en.wikipedia.org/wiki/Semicomputable_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Semicomputable_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.