Вычислимая функция
Вычислимые функции являются основными объектами изучения теории вычислимости . Вычислимые функции являются формализованным аналогом интуитивного понятия алгоритмов в том смысле, что функция вычислима, если существует алгоритм, который может выполнять работу функции, т. е. при заданных входных данных функциональной области он может вернуть соответствующий выходной сигнал. Вычислимые функции используются для обсуждения вычислимости без ссылки на какую-либо конкретную модель вычислений , такую как машины Тьюринга или регистровые машины .. Однако любое определение должно ссылаться на какую-то конкретную модель вычислений, но все допустимые определения дают один и тот же класс функций. Частными моделями вычислимости, которые приводят к множеству вычислимых функций, являются вычислимые по Тьюрингу функции и общие рекурсивные функции .
До точного определения вычислимой функции математики часто использовали неформальный термин « эффективно вычислимая» . С тех пор этот термин стал отождествляться с вычислимыми функциями. Обратите внимание, что эффективная вычислимость этих функций не означает, что они могут быть эффективно вычислены (т.е. вычислены за разумное время). На самом деле, для некоторых эффективно вычисляемых функций можно показать, что любой алгоритм, который их вычисляет, будет очень неэффективным в том смысле, что время работы алгоритма увеличивается экспоненциально (или даже суперэкспоненциально ) с увеличением длины входных данных. Поля допустимой вычислимости ивычислительная сложность изучает функции, которые могут быть вычислены эффективно.
Согласно тезису Черча-Тьюринга , вычислимые функции — это именно те функции, которые можно вычислить с помощью механического вычислительного устройства при неограниченном количестве времени и памяти. Эквивалентно, этот тезис утверждает, что функция вычислима тогда и только тогда, когда у нее есть алгоритм. Обратите внимание, что алгоритм в этом смысле понимается как последовательность шагов, которую может выполнить человек с неограниченным временем и неограниченным запасом ручки и бумаги.
Аксиомы Блюма можно использовать для определения абстрактной теории сложности вычислений на множестве вычислимых функций. В теории вычислительной сложности проблема определения сложности вычислимой функции известна как задача о функции .
Вычислимость функции — неформальное понятие. Один из способов описать это — сказать, что функция вычислима, если ее значение может быть получено с помощью эффективной процедуры . С большей строгостью функция вычислима тогда и только тогда, когда существует эффективная процедура, которая по любому набору k натуральных чисел будет давать значение . [1] В соответствии с этим определением оставшаяся часть этой статьи предполагает, что вычислимые функции принимают в качестве аргументов конечное число натуральных чисел и возвращают значение, являющееся единственным натуральным числом.
В качестве аналогов этому неформальному описанию существует множество формальных математических определений. Класс вычислимых функций может быть определен во многих эквивалентных моделях вычислений , включая