Semicomputable function

In computability theory, a semicomputable function is a partial function $f:\mathbb{\mathbb{Q}}\to \mathbb{ℝ}$ that can be approximated either from above or from below by a computable function. More precisely a partial function $f:\mathbb{\mathbb{Q}}\to \mathbb{ℝ}$ is upper semicomputable, meaning it can be approximated from above, if there exists a computable function $\varphi (x,k):\mathbb{\mathbb{Q}}\times \mathbb{\mathbb{N}}\to \mathbb{\mathbb{Q}}$, where $x$ is the desired parameter for $f(x)$ and $k$ is the level of approximation, such that:

• $\underset{k\to \mathrm{\infty }}{\lim }\varphi (x,k)=f(x)$
• $\mathrm{\forall }k\in \mathbb{\mathbb{N}}:\varphi (x,k+1)\le \varphi (x,k)$

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

• $\underset{k\to \mathrm{\infty }}{\lim }\varphi (x,k)=f(x)$
• $\mathrm{\forall }k\in \mathbb{\mathbb{N}}:\varphi (x,k+1)\ge \varphi (x,k)$

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.