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 está 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}$

Completamente análoga, una función parcial es semicomputable inferior si y solo si es semicomputable superior o de manera equivalente si existe una función computable tal que: ${\ Displaystyle f: \ mathbb {Q} \ rightarrow \ mathbb {R}}$ ${\ Displaystyle -f (x)}$ ${\ Displaystyle \ phi (x, k)}$