Função semicomputável

Na teoria da computabilidade, uma função semicomputável é uma função parcial $f:\mathbb {Q} \rightarrow \mathbb {R}$ que pode ser aproximada tanto por cima quanto por baixo através de uma função computável.
Mais precisamente, uma função parcial $f:\mathbb {Q} \rightarrow \mathbb {R}$ é superiomente semicomputável, significando que ela pode ser aproximada por cima, se existe uma função computável $\phi (x,k):\mathbb {Q} \times \mathbb {N} \rightarrow \mathbb {Q}$, onde $x$ é parámetro desejado para $f(x)$ e $k$ é o nível de aproximação, de modo que:

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

Analogamente, uma função parcial $f:\mathbb {Q} \rightarrow \mathbb {R}$ é inferiormente semicomputável se e somente se $-f(x)$ é superiomente semicomputável ou equivalentemente, se existe uma função computável $\phi (x,k)$ de modo que:

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

Se uma função parcial for superior e inferiormente semicomputável, então ela passará a ser chamada de uma função computável.

Referências

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