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

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

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

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

А общая функция является предельно вычислимым, если существует полная вычислимая функция такой, что

Общая функция является предельно вычислимым в D если есть общая функция вычислим в D также удовлетворяет

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

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

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

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

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

чей предел в качестве уходит в бесконечность - характеристическая функция .

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

Теперь предположим, что вычисление сходится в шаги и смотрит только на первый кусочки . Теперь выберите такой, что для всех . Если тогда вычисление сходится не более чем шаги к . Следовательно имеет предел , так предельно вычислимо.

Поскольку множества - это просто множества, вычислимые из к Теорема Поста, из предельной леммы также следует, что предельные вычислимые множества являются наборы.

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

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

Когда действительное число рассматривается как последовательность битов, справедливо следующее эквивалентное определение. Бесконечная последовательность двоичных цифр вычислима в пределе тогда и только тогда, когда существует полная вычислимая функция принимая значения в наборе так что для каждого я Лимит существует и равно . Таким образом, для каждого я, так как т увеличивает ценность в конечном итоге становится постоянным и равным . Как и в случае вычислимых действительных чисел, невозможно эффективно перемещаться между двумя представлениями предельных вычислимых действительных чисел.

Примеры

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

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

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

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