Полувычислимая функция

В теории вычислимости — полувычислимая функция это частичная функция $f:\mathbb {Q} \rightarrow \mathbb {R}$ которая может быть аппроксимирована либо сверху, либо снизу вычислимой функцией .

Точнее частичная функция $f:\mathbb {Q} \rightarrow \mathbb {R}$ является полувычислимым сверху , то есть его можно аппроксимировать сверху, если существует вычислимая функция $\phi (x,k):\mathbb {Q} \times \mathbb {N} \rightarrow \mathbb {Q}$, где $x$ является желаемым параметром для $f(x)$ и $k$ – уровень аппроксимации, такой, что:

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

Полностью аналогичен частичной функции $f:\mathbb {Q} \rightarrow \mathbb {R}$ полувычислимо снизу тогда и только тогда, когда $-f(x)$ полувычислима сверху или, что то же самое, если существует вычислимая функция $\phi (x,k)$ такой, что:

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

Если частичная функция как сверху, так и снизу, полувычислима она называется вычислимой.

См. также

• Теория вычислимости

Ссылки

• Минг Ли и Пол Витаньи, Введение в колмогоровскую сложность и ее приложения , стр. 37–38, Springer, 1997.