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

Предел равномерно вычислимой последовательности функций

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

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

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

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

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

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

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

Множество натуральных чисел определяется как вычислимое в пределе тогда и только тогда, когда его характеристическая функция вычислима в пределе. Напротив, множество вычислимо тогда и только тогда, когда оно вычислимо в пределе функцией и существует вторая вычислимая функция, которая принимает входные данные i и возвращает значение t, достаточно большое, чтобы стабилизировалось. ${\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}}$

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

Расширение

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

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

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

Когда вещественное число рассматривается как последовательность битов, справедливо следующее эквивалентное определение. Бесконечная последовательность двоичных цифр вычислима в пределе тогда и только тогда, когда существует полная вычислимая функция, принимающая значения в наборе, такая, что для каждого i предел существует и равен . Таким образом, для каждого i с увеличением t значение в конечном итоге становится постоянным и равным . Как и в случае вычислимых вещественных чисел, невозможно эффективно перемещаться между двумя представлениями предельных вычислимых вещественных чисел. ${\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)}$

Примеры

• Действительное число, двоичное разложение которого кодирует проблему остановки , вычислимо в пределе, но не вычислимо.
• Действительное число, двоичное разложение которого кодирует множество истинности арифметики первого порядка, невычислимо в пределе.
• Постоянная Хайтина .

Расширение теории множеств

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

Для заданного допустимого ординала определите -арифметическую иерархию: ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

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

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

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

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

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

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

Ссылки

1. А. Мостовский, «Примеры множеств, определяемых с помощью двух и трех кванторов». Fundamenta Mathematicae т. 42, вып. 2, стр. 259--270 (1955)
2. Г. Крискуоло, Э. Миникоцци, Г. Трауттер, «Предельная рекурсия и арифметическая иерархия». Французское ревю автоматических информационных исследований, Теорическая информатика, книга 9, вып. Р3 (1975), стр. 5–12. Издательство Дюно-Готье-Виллар.
3. SG Simpson, «Теория степеней допустимых ординалов», стр. 170–171. Появляется в J. Fenstad, P. Hinman, Generalized Recursion Theory: Proceedings of the 1972 Oslo Symposium (1974), ISBN  0-7204-22760 .

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