Função semicomputável

Na teoria da computabilidade, uma função semicomputável é uma função parcial $f:\mathbb{Q}\to ℝ$ 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}\to ℝ$ é superiomente semicomputável, significando que ela pode ser aproximada por cima, se existe uma função computável $\varphi (x,k):\mathbb{Q}\times \mathbb{N}\to \mathbb{Q}$, onde $x$ é parámetro desejado para $f(x)$ e $k$ é o nível de aproximação, de modo que:

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

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

• $\underset{k\to \mathrm{\infty }}{\lim }\varphi (x,k)=f(x)$
• $\mathrm{\forall }k\in \mathbb{N}:\varphi (x,k+1)\ge \varphi (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.