title: Semicomputable function
text: # 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 if and only if $-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.
  
  