Введение
Лимит равномерно вычислимой последовательности функций
В теории вычислимости функция называется предельно вычислимой, если она является пределом равномерно вычислимой последовательности функций. Также используются термины "вычисляемые в пределе", "предельно рекурсивные" и "рекурсивно приближаемые". Предельно вычислимые функции можно представить как те, для которых существует вычислимая процедура угадывания, которая в конечном итоге выдает правильное значение. Множество является предельно вычислимым тогда и только тогда, когда его характеристическая функция предельно вычислима. Если последовательность равномерно вычислима относительно D, то функция является предельно вычислимой относительно D.
In computability theory, a function is called limit computable if it is the limit of a uniformly computable sequence of functions. The terms computable in the limit, limit recursive and recursively approximable are also used. One can think of limit computable functions as those admitting an eventually correct computable guessing procedure at their true value. A set is limit computable just when its characteristic function is limit computable. If the sequence is uniformly computable relative to D, then the function is limit computable in D.
Граничная лемма
Лемма о пределах утверждает, что множество натуральных чисел является предельно вычислимым тогда и только тогда, когда оно вычислимо из (прыжка Тьюринга пустого множества). Релятивизированная лемма о пределах утверждает, что множество является предельно вычислимым в отношении тогда и только тогда, когда оно вычислимо из . Кроме того, лемма о пределах (и ее релятивизация) выполняются равномерно. Таким образом, можно перейти от индекса функции к индексу относительно . Также можно перейти от индекса относительно к индексу некоторого , обладающего пределом .
Расширение
Итерация предельной вычислимости может быть использована для продвижения по арифметической иерархии. А именно, функция от *n* аргументов вычислима, если и только если она может быть записана в виде для некоторой рекурсивной функции от *n* аргументов \(g\), при условии существования всех пределов.
Предельные вычислимые действительные числа
Реальное число x вычислимо в пределе, если существует вычислимая последовательность рациональных чисел (или, что эквивалентно, вычислимых действительных чисел), сходящаяся к x. В отличие от этого, реальное число вычислимо тогда и только тогда, когда существует последовательность рациональных чисел, сходящаяся к нему, и имеющая вычислимый модуль сходимости. Если реальное число рассматривается как последовательность битов, то выполняется следующее эквивалентное определение: бесконечная последовательность двоичных цифр вычислима в пределе, если и только если существует полная вычислимая функция, принимающая значения в множестве {0, 1}, такая, что для каждого i существует предел и он равен aᵢ. Таким образом, для каждого i, при увеличении t значение aᵢ в конечном итоге становится постоянным и равным aᵢ. Как и в случае вычислимых действительных чисел, невозможно эффективно переходить между двумя представлениями предельно вычислимых действительных чисел.
Примеры
Реальное число, двоичное разложение которого кодирует проблему останова, вычислимо в пределе, но не вычислимо. Реальное число, двоичное разложение которого кодирует множество истинных утверждений арифметики первого порядка, не вычислимо в пределе. Постоянная Чейтина.