Función semicomputable

En la teoría de la computabilidad , una función semicomputable es una función parcial.${\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }$que puede aproximarse tanto desde arriba como desde abajo mediante una función computable .

Más precisamente, una función parcial${\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }$es semicomputable superior , lo que significa que puede aproximarse desde arriba, si existe una función computable.${\displaystyle \phi (x,k):\mathbb {Q} \times \mathbb {N} \rightarrow \mathbb {Q} }$, dónde${\displaystyle x}$es el parámetro deseado para${\displaystyle f(x)}$y${\displaystyle k}$es el nivel de aproximación, de tal manera 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)}

Completamente análogo a una función parcial${\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }$es semicomputable inferior si y solo si${\displaystyle -f(x)}$es semicomputable superior o equivalentemente si existe una función computable${\displaystyle \phi (x,k)}$de tal manera 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)}

Si una función parcial es semicomputable tanto superior como inferiormente, se denomina computable.

• teoría de la computabilidad

• Ming Li y Paul Vitányi, Introducción a la complejidad de Kolmogorov y sus aplicaciones , págs. 37-38 , Springer, 1997.