Semicomputable function

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

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

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

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

See also

• Computability theory

References

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