Расчет в пределе - Computation in the limit

В теория вычислимости, функция называется предел вычислимости если это предел равномерно вычислимой последовательности функций. Условия вычислимый в пределе, ограничить рекурсивный и рекурсивно аппроксимируемый также используются. Можно думать о предельных вычислимых функциях как о тех, которые допускают в конечном итоге правильную вычислимую процедуру угадывания их истинного значения. Множество предельно вычислимо только тогда, когда его характеристическая функция предельно вычислимо.

Если последовательность равномерно вычислима относительно D, то функция предел вычислимости в D.

Формальное определение

А общая функция ${\displaystyle r(x)}$ является предельно вычислимым, если существует полная вычислимая функция ${\displaystyle {\hat {r}}(x,s)}$ такой, что

${\displaystyle \displaystyle r(x)=\lim _{s\to \infty }{\hat {r}}(x,s)}$

Общая функция ${\displaystyle r(x)}$ является предельно вычислимым в D если есть общая функция ${\displaystyle {\hat {r}}(x,s)}$ вычислим в D также удовлетворяет

${\displaystyle \displaystyle r(x)=\lim _{s\to \infty }{\hat {r}}(x,s)}$

Набор натуральные числа определяется как вычислимая в пределе тогда и только тогда, когда его характеристическая функция вычислимо в пределе. Напротив, набор вычислимый тогда и только тогда, когда он вычислим в пределе функцией ${\displaystyle \phi (t,i)}$ и есть вторая вычислимая функция, которая принимает входные данные я и возвращает значение т достаточно большой, чтобы ${\displaystyle \phi (t,i)}$ стабилизировалась.

Предельная лемма

В предельная лемма утверждает, что набор натуральных чисел является предельно вычислимым тогда и только тогда, когда набор вычислим из ${\displaystyle 0'}$ (в Прыжок Тьюринга пустого набора). Релятивизированная предельная лемма утверждает, что множество предельно вычислимо в ${\displaystyle D}$ тогда и только тогда, когда это вычислимо из ${\displaystyle D'}$Более того, предельная лемма (и ее релятивизация) справедливы равномерно. Таким образом, можно перейти от индекса функции ${\displaystyle {\hat {r}}(x,s)}$ к индексу для ${\displaystyle {\hat {r}}(x)}$ относительно ${\displaystyle 0'}$. Также можно перейти из индекса для ${\displaystyle {\hat {r}}(x)}$ относительно ${\displaystyle 0'}$ в указатель для некоторых ${\displaystyle {\hat {r}}(x,s)}$ это имеет предел ${\displaystyle {\hat {r}}(x)}$.

Доказательство

В качестве ${\displaystyle 0'}$ является [вычислимо перечислимым] множеством, оно должно быть вычислимым в самом пределе, поскольку вычислимая функция может быть определена

${\displaystyle \displaystyle {\hat {r}}(x,s)={\begin{cases}1&{\text{if by stage }}s,x{\text{ has been enumerated into }}0'\\0&{\text{if not}}\end{cases}}}$

чей предел ${\displaystyle r(x)}$ в качестве ${\displaystyle s}$ уходит в бесконечность - характеристическая функция ${\displaystyle 0'}$.

Поэтому достаточно показать, что если предельная вычислимость сохраняется Редукция Тьюринга, так как это покажет, что все множества, вычислимые из ${\displaystyle 0'}$ предельно вычислимы. Наборы исправлений ${\displaystyle X,Y}$ которые отождествляются со своими характеристическими функциями и вычислимой функцией ${\displaystyle X_{s}}$ с лимитом ${\displaystyle X}$. Предположим, что ${\displaystyle Y(z)=\phi ^{X}(z)}$ для некоторого сокращения Тьюринга ${\displaystyle \phi }$ и определим вычислимую функцию ${\displaystyle Y_{s}}$ следующее

${\displaystyle \displaystyle Y_{s}(z)={\begin{cases}\phi ^{X_{s}}(z)&{\text{if }}\phi ^{X_{s}}{\text{ converges in at most }}s{\text{ steps.}}\\0&{\text{otherwise }}\end{cases}}}$

Теперь предположим, что вычисление ${\displaystyle \phi ^{X}(z)}$ сходится в ${\displaystyle s}$ шаги и смотрит только на первый ${\displaystyle s}$ кусочки ${\displaystyle X}$. Теперь выберите ${\displaystyle s'>s}$ такой, что для всех ${\displaystyle z<s+1}$ ${\displaystyle X_{s'}(z)=X(z)}$. Если ${\displaystyle t>s'}$ тогда вычисление ${\displaystyle \phi ^{X_{t}}(z)}$ сходится не более чем ${\displaystyle s'<t}$ шаги к ${\displaystyle \phi ^{X}(z)}$. Следовательно ${\displaystyle Y_{s}(z)}$ имеет предел ${\displaystyle \phi ^{X}(z)=Y(z)}$, так ${\displaystyle Y}$ предельно вычислимо.

Поскольку ${\displaystyle \Delta _{2}^{0}}$ множества - это просто множества, вычислимые из ${\displaystyle 0'}$ к Теорема Поста, из предельной леммы также следует, что предельные вычислимые множества являются ${\displaystyle \Delta _{2}^{0}}$ наборы.

Ограничьте вычислимые действительные числа

А настоящий номер Икс является вычислимо в пределе если существует вычислимая последовательность ${\displaystyle r_{i}}$ из рациональное число (или, что эквивалентно, вычислимые действительные числа ) который сходится к Икс. Напротив, реальное число вычислимый тогда и только тогда, когда существует последовательность рациональных чисел, которая сходится к ней и которая имеет вычислимую модуль сходимости.

Когда действительное число рассматривается как последовательность битов, справедливо следующее эквивалентное определение. Бесконечная последовательность ${\displaystyle \omega }$ двоичных цифр вычислима в пределе тогда и только тогда, когда существует полная вычислимая функция ${\displaystyle \phi (t,i)}$ принимая значения в наборе ${\displaystyle \{0,1\}}$ так что для каждого я Лимит ${\displaystyle \lim _{t\rightarrow \infty }\phi (t,i)}$ существует и равно ${\displaystyle \omega (i)}$. Таким образом, для каждого я, так как т увеличивает ценность ${\displaystyle \phi (t,i)}$ в конечном итоге становится постоянным и равным ${\displaystyle \omega (i)}$. Как и в случае вычислимых действительных чисел, невозможно эффективно перемещаться между двумя представлениями предельных вычислимых действительных чисел.

Примеры

• Реальное число, двоичное расширение которого кодирует проблема остановки вычислимо в пределе, но не вычислимо.
• Реальное число, двоичное расширение которого кодирует набор истинности арифметика первого порядка не вычислимо в пределе.

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

• Последовательность Спекера

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

1. Дж. Шмидхубер, "Иерархии обобщенных колмогоровских сложностей и неисчислимые универсальные меры, вычислимые в пределе", Международный журнал основ информатики, 2002.
2. Р. Соаре. Рекурсивно перечислимые множества и степени. Springer-Verlag 1987.