WikiDer > Вычисление в пределе - Википедия

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

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

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

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

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

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

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

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

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

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

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

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

${ displaystyle displaystyle { hat {r}} (x, s) = { begin {cases} 1 & { text {if by stage}} s, x { text {был пронумерован в}} 0 ' 0 & { text {если нет}} end {case}}}$

чей предел ${ Displaystyle г (х)}$ в качестве ${ 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 {case} phi ^ {X_ {s}} (z) & { text {if}} phi ^ {X_ {s}} { text {сходится не более чем за}} s { text {шаги.}} 0 & { text {в противном случае}} end {case}}}$

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

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

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