Вычислимая функция

редактировать

Математическая функция, которая может быть вычислена программой

Вычислимые функции являются основными объектами изучения в теория вычислимости. Вычислимые функции являются формализованным аналогом интуитивного понятия алгоритмов в том смысле, что функция является вычислимой, если существует алгоритм, который может выполнять работу функции, т. Е. С учетом входных данных области определения функции. может вернуть соответствующий вывод. Вычислимые функции используются для обсуждения вычислимости без ссылки на какую-либо конкретную модель вычислений, такую как машины Тьюринга или регистровые машины. Однако любое определение должно ссылаться на некоторую конкретную модель вычислений, но все действительные определения дают один и тот же класс функций. Конкретные модели вычислимости, которые дают начало множеству вычислимых функций, - это вычислимые по Тьюрингу функции и μ-рекурсивные функции.

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

Согласно тезису Черча – Тьюринга, вычислимые функции - это именно те функции, которые могут быть вычислены с использованием механического вычислительного устройства при неограниченном количестве времени и памяти. Эквивалентно, этот тезис утверждает, что функция вычислима тогда и только тогда, когда у нее есть алгоритм. Обратите внимание, что алгоритм в этом смысле понимается как последовательность шагов, которую может выполнить человек с неограниченным временем и неограниченным запасом ручки и бумаги.

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

Содержание

1 Определение
2 Характеристики вычислимых функций
3 Вычислимые множества и отношения
4 Формальные языки
5 Примеры
6 Тезис Черча – Тьюринга
7 Доказуемость
- 7.1 Связь с рекурсивно определенными функциями
- 7.2 Суммарные функции, которые не являются доказуемо совокупными
8 Невычислимые неразрешимые задачи
9 Расширения вычислимости
- 9.1 Относительная вычислимость
- 9.2 Высшая теория рекурсии
- 9.3 Гипервычисления
10 См. также
11 Ссылки

Определение

Вычислимость функции - понятие неформальное. Один из способов описать это - сказать, что функция вычислима, если ее значение может быть получено с помощью эффективной процедуры. С большей строгостью функция $f: N k → N {\ displaystyle f: \ mathbb {N} ^ {k} \ rightarrow \ mathbb {N}}$ $f: {\ mathbb N} ^ {k} \ rightarrow {\ mathbb N}$ вычислима тогда и только тогда, когда существует является эффективной процедурой, которая для любого k- кортежа $x {\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ натуральных чисел даст значение $f (x) {\ Displaystyle F (\ mathbf {x})}$ $f ({\ mathbf x})$ . В соответствии с этим определением в оставшейся части статьи предполагается, что вычислимые функции принимают конечное число натуральных чисел в качестве аргументов и производят значение, которое является единственным натуральным числом.

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

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

Например, можно формализовать вычислимые функции как μ-рекурсивные функции, которые являются частичными функциями, которые принимают конечные кортежи из натуральных чисел и возвращают одно натуральное число (как указано выше). Это наименьший класс частичных функций, который включает в себя функции константы, преемника и проекции, и является закрытым в рамках композиция, примитивная рекурсия и μ оператор.

Эквивалентно вычислимые функции могут быть формализованы как функции, которые могут быть вычислены идеализированным вычислительным агентом, таким как машина Тьюринга или регистровая машина. Формально говоря, частичная функция $f: N k → N {\ displaystyle f: \ mathbb {N} ^ {k} \ rightarrow \ mathbb {N}}$ $f: {\ mathbb N} ^ {k} \ rightarrow {\ mathbb N}$ может вычисляться тогда и только тогда, когда существует компьютерная программа со следующими свойствами:

Если определен $f (x) {\ displaystyle f (\ mathbf {x})}$ $f ({\ mathbf x})$ , то программа завершится при вводе $x {\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ со значением $f (x) {\ displaystyle f (\ mathbf {x})}$ $f ({\ mathbf x})$ хранится в памяти компьютера.
Если $f (x) {\ displaystyle f (\ mathbf {x})}$ $f ({\ mathbf x})$ не определено, то программа никогда не завершается вход $x {\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ .

Характеристики вычислимых функций

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

Enderton [1977] дает следующие характеристики процедуры для вычисления вычислимой функции; аналогичные характеристики были даны Тьюрингом [1936], Роджерсом [1967] и другими.

«Для процедуры должны быть точные инструкции (т.е. программа) конечной длины». Таким образом, каждая вычислимая функция должна иметь конечную программу, полностью описывающую, как функция должна быть вычислена. Можно вычислить функцию, просто следуя инструкциям; не требуется никаких предположений или специального понимания.
«Если процедуре задан кортеж из k x в области f, то после конечного числа дискретных шагов процедура должна завершиться и произвести f (x ). " Интуитивно процедура выполняется шаг за шагом с определенным правилом, описывающим, что делать на каждом этапе расчета. Только конечное число шагов может быть выполнено до того, как значение функции будет возвращено.
"Если процедуре задан кортеж из k x, который не находится в области f, тогда процедура может продолжаться бесконечно, никогда не останавливаясь, или может застрять в какой-то момент (т. е. одна из ее инструкций не может быть выполнена), но она не должна претендовать на получение значения для f на x . " Таким образом, если значение для f (x ) когда-либо найдено, оно должно быть правильным значением. Вычислительному агенту нет необходимости отличать правильные результаты от неправильных, потому что процедура определяется как правильная тогда и только тогда, когда она дает результат.

Далее Эндертон перечисляет несколько пояснений этих трех требований процедуры для вычислимая функция:

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

Подводя итог, на основе этого представления функция является вычислимой, если: (a) дан вход из ее домена, возможно, полагаясь на неограниченный пространство памяти, он может выдавать соответствующий результат, следуя процедуре (программе, алгоритму), которая формируется конечным числом точных однозначных инструкций; (б) он возвращает такой результат (остановки) за конечное число шагов; и (c) если задан ввод, не входящий в его домен, он либо никогда не останавливается, либо застревает.

Поле вычислительной сложности изучает функции с заданными границами времени и / или пространства, разрешенными для успешного вычисления.

Вычислимые множества и отношения

Набор Aнатуральных чисел называется вычислимым (синонимы: рекурсивный, разрешимая ), если существует вычислимая общая функция f такая, что для любого натурального числа n, f (n) = 1, если nравно в Aи f (n) = 0, если nне входит в A.

Набор натуральных чисел называется вычислимо перечислимым (синонимы: рекурсивно перечислимый, полуразрешимый ), если существует вычислимая функция f такая, что для каждого числа n, f (n) определяется тогда и только тогда, когда nнаходится в наборе. Таким образом, набор вычислимо перечислим тогда и только тогда, когда он является областью определения некоторой вычислимой функции. Слово enumerable используется потому, что следующие значения эквивалентны для непустого подмножества Bнатуральных чисел:

B- это область вычислимой функции.
B- это диапазон полной вычислимой функции. Если Bбесконечно, то функцию можно считать инъективной.

Если набор Bявляется диапазоном функции f, тогда функцию можно рассматривать как перечисление B, потому что список f (0), f (1),... будет включать каждый элемент B.

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

Формальные языки

В теории вычислимости в информатике принято рассматривать формальные языки. алфавит - произвольный набор. Слово в алфавите - это конечная последовательность символов алфавита; один и тот же символ может использоваться более одного раза. Например, двоичные строки - это в точности слова в алфавите {0, 1}. язык - это подмножество набора всех слов фиксированного алфавита. Например, набор всех двоичных строк, содержащих ровно 3 единицы, представляет собой язык над двоичным алфавитом.

Ключевым свойством формального языка является уровень сложности, необходимый для определения того, присутствует ли данное слово в языке. Должна быть разработана некоторая система кодирования, позволяющая вычислимой функции принимать произвольное слово на языке в качестве входных; это обычно считается рутиной. Язык называется вычислимым (синонимы: рекурсивный, разрешимый ), если существует вычислимая функция f такая, что для каждого слова wбольше алфавит, f (w) = 1, если слово на языке и f (w) = 0, если слово не на языке. Таким образом, язык является вычислимым, если существует процедура, которая может правильно определить, есть ли в языке произвольные слова.

Язык является вычислимо перечислимым (синонимы: рекурсивно перечислимым, полуразрешимым ), если существует вычислимая функция f такая, что f (w) определяется тогда и только тогда, когда слово wприсутствует в языке. Термин перечислимый имеет ту же этимологию, что и в вычислимо перечислимых наборах натуральных чисел.

Примеры

Следующие функции вычислимы:

Каждая функция с конечной областью ; например, любая конечная последовательность натуральных чисел.
Каждая постоянная функция f: N→ N, f (n 1,... n k): = n.
Сложение f: N→ N, f (n 1,n2): = n 1 + n 2
наибольший общий делитель двух чисел
A коэффициент Безу двух чисел
Наименьший простой множитель числа

Если f и g вычислимы, то вычислимы: f + g, f * g, $f ∘ g {\ displaystyle f \ circ g}$ $f \ circ g$ , если f равно унарный, max (f, g), min (f, g), arg max {y ≤ f (x)} и многие другие комбинации.

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

Функция f такая, что f (n) = 1, если есть последовательность из не менее n последовательных пятерок в десятичном разложении π, и f (n) = 0 в противном случае, является вычислимой. (Функция f является либо функцией константы 1, которая является вычислимой, либо существует k такое, что f (n) = 1, если n < k and f(n) = 0 if n ≥ k. Every such function is computable. It is not known whether there are arbitrarily long runs of fives in the decimal expansion of π, so we don't know which of those functions is f. Nevertheless, we know that the function f must be computable.)
Каждый конечный сегмент невычислимой последовательности натуральных чисел (например, Функция занятого Бивера Σ) вычислима. Например, для каждого натурального числа n существует алгоритм, вычисляющий конечную последовательность Σ (0), Σ (1), Σ (2),..., Σ (n) - в отличие от того факта, что не существует алгоритма, который вычисляет всю Σ-последовательность, то есть Σ (n) для всех n. Таким образом, «Print 0, 1, 4, 6, 13» является тривиальным алгоритмом для вычисления Σ (0), Σ (1), Σ (2), Σ (3), Σ (4); аналогично, для любого заданного значения n существует такой тривиальный алгоритм (даже если он никогда не может быть известен или создан кем-либо).) для вычисления Σ (0), Σ (1), Σ (2),..., Σ (n).

тезис Чёрча-Тьюринга

тезис Чёрча-Тьюринга утверждает, что любая функция, вычисляемая из процедуры, обладающей тремя свойствами, перечисленными выше, является вычислимой функцией. Поскольку эти три свойства формально не определены, Тезис Черча – Тьюринга нельзя доказать. В качестве доказательства тезиса часто используются следующие факты:

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

Тезис Чёрча – Тьюринга иногда используется в доказательствах, чтобы обосновать вычислимость конкретной функции, давая конкретное описание процедура вычисления. Это разрешено, потому что считается, что все подобные варианты использования тезиса могут быть устранены утомительным процессом написания формальной процедуры для функции в некоторой модели вычислений.

Обеспечиваемость

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

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

Связь с рекурсивно определенными функциями

В функции, определенной рекурсивным определением, каждое значение определяется фиксированной формулой первого порядка других, ранее определенных значений та же функция или другие функции, которые могут быть просто константами. Подмножество из них - примитивные рекурсивные функции . Каждая такая функция доказуемо является полной: для такой k-арной функции f каждое значение $f (n 1, n 2... nk) {\ displaystyle f (n_ {1}, n_ {2}... n_ {k})}$ ${\ displaystyle f (n_ {1}, n_ {2}... n_ {k})}$ можно вычислить, следуя определению в обратном порядке, итеративно, и после конечного числа итераций (как можно легко доказать) достигается константа.

Обратное неверно, так как не каждая доказуемо итоговая функция является примитивно рекурсивной. В самом деле, можно перечислить все примитивные рекурсивные функции и определить функцию en так, что для всех n m: en (n, m) = f n (m), где f n - n-я примитивная рекурсивная функция (для k-арных функций будет установлено значение f n (m, m... m)). Теперь, g (n) = en (n, n) +1 доказуемо полное, но не примитивно рекурсивное, с помощью аргумента диагонализация : если бы был aj такой, что g = f j, мы получили бы g (j) = en (j, j) +1 = f j (j) + 1 = g (j) +1; противоречие. (Гёделевские числа всех примитивно рекурсивных функций могут быть перечислены с помощью примитивно рекурсивной функции, хотя значения примитивных рекурсивных функций не могут.)

Одна такая функция, которая доказуема всего, но не примитивно рекурсивной является функция Аккермана : поскольку она определена рекурсивно, действительно легко доказать ее вычислимость (однако аналогичный аргумент диагонализации также может быть построен для всех функций, определенных рекурсивным определением; таким образом, существует являются доказуемыми полными функциями, которые не могут быть определены рекурсивно).

Суммарные функции, которые не являются доказуемо итоговыми

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

Если все вычислимые функции перечисляются с помощью машин Тьюринга, которые их создают, то приведенное выше утверждение может быть показано, если система доказательства работает, с помощью аргумента диагонализации, аналогичного тому, который использовался выше, с использованием перечисления доказуемо суммарные функции, данные ранее. Один использует машину Тьюринга, которая перечисляет соответствующие доказательства, и для каждого ввода n вызывает f n (n) (где f n - n-я функция по этому перечислению), вызывая Машина Тьюринга, вычисляющая его согласно n-му доказательству. Такая машина Тьюринга гарантированно остановится, если система доказательства работоспособна.

Невычислимые функции и неразрешимые проблемы

Каждая вычислимая функция имеет конечную процедуру, дающую явные, однозначные инструкции о том, как ее вычислить. Кроме того, эта процедура должна быть закодирована в конечном алфавите, используемом вычислительной моделью, поэтому существует только счетно вычислимых функций. Например, функции могут быть закодированы с использованием строки битов (алфавит Σ = {0, 1}).

Действительные числа не поддаются исчислению, поэтому большинство действительных чисел не поддаются вычислению. См. вычислимое число. Набор конечных функций для натуральных чисел неисчислим, поэтому большинство из них не вычислимы. Конкретными примерами таких функций являются Занят бобер, сложность Колмогорова или любая функция, которая выводит цифры невычислимого числа, например, константа Чейтина.

Аналогично, большинство подмножеств натуральных чисел не вычислимы. Задача остановки была первым таким набором, который был создан. Entscheidungsproblem, предложенная Дэвидом Гильбертом, спрашивает, существует ли эффективная процедура для определения того, какие математические утверждения (закодированные как натуральные числа) верны. Тьюринг и Черч независимо друг от друга показали в 1930-х годах, что этот набор натуральных чисел не вычислим. Согласно тезису Чёрча – Тьюринга, не существует эффективной процедуры (с алгоритмом), которая могла бы выполнять эти вычисления.

Расширения вычислимости

Относительная вычислимость

Понятие вычислимости функции может быть релятивизировано до произвольного набора из натуральные числа А. Функция f определяется как вычислимая в A (эквивалентно A-вычислима или вычислима относительно A ), когда она удовлетворяет определению вычислимой функции с модификациями разрешение доступа к A как к оракулу. Как и в случае с концепцией вычислимой функции, относительной вычислимости можно дать эквивалентные определения во многих различных моделях вычислений. Обычно это достигается путем дополнения модели вычислений дополнительной примитивной операцией, которая спрашивает, является ли данное целое число членом A. Мы также можем говорить о том, что f вычислимо в g, отождествляя g с его графом.

Теория высшей рекурсии

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

Гипервычисление

Хотя тезис Черча – Тьюринга утверждает, что вычислимые функции включают в себя все функции с алгоритмами, можно рассмотреть более широкие классы функций, которые ослабляют требования, которыми должны обладать алгоритмы. Область Hypercomputation изучает модели вычислений, которые выходят за рамки обычных вычислений Тьюринга.

См. Также

Ссылки

Катленд, Найджел. Вычислимость. Cambridge University Press, 1980.
Эндертон, Х.Б. Элементы теории рекурсии. Справочник по математической логике (Северная Голландия, 1977), стр. 527–566.
Роджерс, Х. Теория рекурсивных функций и эффективных вычислений (МакГроу – Хилл, 1967).
Тьюринг, А. (1937), О вычислимых числах, с приложением к Entscheidungsproblem. Труды Лондонского математического общества, серия 2, том 42 (1937), стр.230–265. Перепечатано в M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.