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

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

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

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

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

• ${displaystyle lim _{kightarrow infty }phi (x,k)=f(x)}$
• ${displaystyle forall kin mathbb {N} :phi (x,k+1)geq phi (x,k)}$

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

Смотрите также

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

Рекомендации

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