Расчет в пределе
В теории вычислимости функция называется предельно вычислимой , если она является пределом равномерно вычислимой последовательности функций. Также используются термины вычислимый в пределе , предельно рекурсивный и рекурсивно аппроксимируемый . Можно думать о предельных вычислимых функциях как о тех, которые допускают в конечном итоге правильную вычислимую процедуру угадывания их истинного значения. Множество предельно вычислимо тогда, когда его характеристическая функция предельно вычислима.
Суммарная функция предельно вычислима, если существует тотальная вычислимая функция такая, что
Суммарная функция предельно вычислима в D , если существует вычислимая в D тотальная функция, также удовлетворяющая
Множество натуральных чисел считается вычислимым в пределе тогда и только тогда, когда его характеристическая функция вычислима в пределе. Напротив, множество вычислимо тогда и только тогда, когда оно вычислимо в пределе с помощью функции и существует вторая вычислимая функция, которая принимает ввод i и возвращает значение t , достаточно большое, чтобы стабилизировалось.
Лемма о пределе утверждает, что множество натуральных чисел предельно вычислимо тогда и только тогда, когда это множество вычислимо из ( прыжка Тьюринга пустого множества). Лемма об относительном пределе утверждает, что множество предельно вычислимо в тогда и только тогда, когда оно вычислимо из . Более того, предельная лемма (и ее релятивизация) выполняются равномерно. Таким образом, можно перейти от индекса функции к индексу относительно . Можно также перейти от индекса для относительного к индексу для некоторого с ограничением .
