Вычисление в пределе

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

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

Формальное определение [ править ]

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

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

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

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

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

Предельная лемма [ править ]

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

Доказательство [ править ]

Как $0'$ представляет собой [вычислимо перечислимое] множество, оно должно быть вычислимо в самом пределе, поскольку можно определить вычислимую функцию

\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}}

чей предел $r(x)$ как $s$ стремится к бесконечности, является характеристической функцией $0'$ .

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

\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}}

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

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

Ранний результат, предвещающий эквивалентность предельной вычислимости с $\Delta _{2}^{0}$ -ность была предсказана Мостовским в 1954 году, используя иерархию $\mathbf {P} _{2}^{(1)}$ и формулы $\exists y(\lim _{x\to \infty }10^{-x}\gamma (x,y)<1)$ , где $\gamma (x,y)$ — функция, полученная из произвольной примитивно-рекурсивной функции $\varrho$ такой, что $\exists p\forall s(\varrho (p,s,y)=0)$ эквивалентно $\exists x_{0}\forall x(x>x_{0}\implies \gamma (x,y)=0)$ . ^[1]

Расширение [ править ]

Итерацию предельной вычислимости можно использовать для подъема вверх по арифметической иерархии. А именно, $m$ -арная функция $f(x_{1},\ldots ,x_{m})$ является $\Delta _{k+1}^{0}$ если это можно записать в виде $\lim _{n_{k}}\lim _{n_{k-1}}\ldots \lim _{n_{1}}g(x_{1},\ldots ,x_{m},n_{k},\ldots ,n_{1})$ для некоторых $m+k$ -арная рекурсивная функция $g$ в предположении, что все пределы существуют. ^[2]

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

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

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

Примеры [ править ]

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

Теоретико-множественное расширение [ править ]

Существует модифицированная версия предельной леммы для теории α-рекурсии через функции из $\alpha$ -арифметическая иерархия, представляющая собой иерархию, определенную относительно некоторого допустимого порядкового номера. $\alpha$ . ^[3]

Для данного допустимого ординала $\alpha$ , определить $\alpha$ -арифметическая иерархия:

Отношение $R$ на $\alpha$ является ${\boldsymbol {\Sigma }}_{0}$ если это так $\alpha$ -рекурсивный.
$R$ является ${\boldsymbol {\Sigma }}_{n+1}$ если это проекция ${\boldsymbol {\Pi }}_{n}$ связь.
$R$ является ${\boldsymbol {\Pi }}_{n}$ если его дополнение ${\boldsymbol {\Sigma }}_{n}$ .

Позволять $f$ быть частичной функцией от $\alpha$ к $\alpha$ . Следующие действия эквивалентны:

(График) $f$ является ${\boldsymbol {\Sigma }}_{2}$ .
$f$ слабо $\alpha$ -рекурсивный в ${\boldsymbol {0}}^{\prime }$ , $\alpha$ -прыжок $\emptyset$ используя индексы $\alpha$ -вычислимые функции.
Существует $\alpha$ -рекурсивная функция $f':\alpha \times \alpha \to \alpha$ аппроксимирующий $f$ такой, что $f(\gamma )\simeq \lim _{\sigma \to \alpha }f'(\sigma ,\gamma )$ .

$f\simeq g$ означает, что либо $f(x)$ и $g(x)$ оба не определены, или они оба определены и равны.

См. также [ править ]

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

Ссылки [ править ]

^ А. Мостовский, « Примеры множеств, определяемых с помощью двух и трех кванторов ». Fundamenta Mathematicae, том. 42, вып. 2, стр. 259--270 (1955).
^ Г. Крискуоло, Э. Миникоцци, Г. Трауттер, « Предельная рекурсия и арифметическая иерархия ». Французский журнал операционных исследований компьютерной автоматизации, Теоретическая информатика, книга 9, вып. Р3 (1975), стр. 5–12. Издательство Дюно-Готье-Виллар.
^ С.Г. Симпсон, «Теория степеней допустимых ординалов», стр. 170–171. Появился в книге Дж. Фенстада, П. Хинмана, «Обобщенная теория рекурсии: материалы симпозиума в Осло 1972 года» (1974), ISBN 0-7204-22760 .

Дж. Шмидхубер , «Иерархии обобщенных колмогоровских сложностей и неисчислимые универсальные меры, вычислимые в пределе», Международный журнал основ компьютерных наук , 2002, дои : 10.1142/S0129054102001291 .
Р. Соаре . Рекурсивно перечислимые множества и степени . Спрингер-Верлаг 1987.
В. Браттка. Связь Галуа между скачками Тьюринга и пределами . Бревно. Методы вычислений. наук. , 2018, дои : 10.23638/LMCS-14(3:13)2018 .

[1] А. Мостовский, « Примеры множеств, определяемых с помощью двух и трех кванторов ». Fundamenta Mathematicae, том. 42, вып. 2, стр. 259--270 (1955).

[2] Г. Крискуоло, Э. Миникоцци, Г. Трауттер, « Предельная рекурсия и арифметическая иерархия ». Французский журнал операционных исследований компьютерной автоматизации, Теоретическая информатика, книга 9, вып. Р3 (1975), стр. 5–12. Издательство Дюно-Готье-Виллар.

[3] С.Г. Симпсон, «Теория степеней допустимых ординалов», стр. 170–171. Появился в книге Дж. Фенстада, П. Хинмана, «Обобщенная теория рекурсии: материалы симпозиума в Осло 1972 года» (1974), ISBN 0-7204-22760 .

[1]

[2]

[3]