Função semicomputável

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

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

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

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