Función semicomputable

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

Más precisamente, una función parcial es semicomputable superior , lo que significa que se puede aproximar desde arriba, si existe una función computable , donde es el parámetro deseado para y es el nivel de aproximación, tal que: ${\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} }$ ${\displaystyle \phi (x,k):\mathbb {Q} \times \mathbb {N} \rightarrow \mathbb {Q} }$ ${\displaystyle x}$ ${\displaystyle f(x)}$ ${\displaystyle k}$

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

• ${\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 tanto semicomputable superior como inferior, se denomina computable.

Véase también

• Teoría de la computabilidad

Referencias

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