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

Вычисли́мые фу́нкции^[1] — множество функций то есть отображения множества натуральных чисел во множество натуральных чисел, в математических обозначениях это $f\colon N\to N,$ которые могут быть реализованы некоторым, алгоритмом, описание которого конечно, например, описанием переходов некоторой машиной Тьюринга.

Функции $f$ называют алгоритмически разрешимыми или алгоритмически неразрешимыми, в зависимости от того, возможен ли некоторый теоретический алгоритм, вычисляющий эту функцию за конечное время.

В упрощённом виде в качестве множества $N$ обычно рассматривается множество $B^{*}$ — множество слов в двоичном алфавите $B=\{0,1\}$ . Это не снижает общности рассмотрения функций с точки зрения разрешимости, если результатом вычисления может быть не только некоторое слово, но и специальное значение — «неопределённость», соответствующее случаю, когда алгоритм вычисления аргумента функции на некотором множестве аргументов «зависает» — то есть никогда не выдает результат. Таким образом, можно дать следующее определение вычислимой функции $N$ :

$N=B^{*}\cup \{\operatorname {undef} \},$

где $B=\{0,1\}$ , а $\operatorname {undef}$ — специальный элемент, означающий неопределённость.

Роль множества $N$ может играть множество натуральных чисел, к которому добавлен элемент $\operatorname {undef}$ , и тогда вычислимые функции — это некоторое подмножество натуральнозначных функций натурального аргумента.

Непринципиально, что в качестве аргументов $N$ могут выступать различные счётные множества, например, — множество натуральных чисел, множество рациональных чисел, множество слов в каком-либо конечном алфавите и др. Важно, чтобы существовал некоторый формальный язык в конечном алфавите описания элементов множества $N$ и чтобы задача распознавания корректных описаний аргументов была вычислима. Например, для описания натуральных чисел удобно использовать двоичную систему счисления — язык описания натуральных чисел в алфавите $B$ , но это совсем необязательно.

В качестве исполнителя алгоритма вместо машин Тьюринга можно взять один из иных Тьюринг-полных исполнителей. Грубо говоря, «абстрактным исполнителем» алгоритма может быть некоторый гипотетический компьютер, подобный персональным компьютерам, но с актуально бесконечным объёмом памяти и архитектурой, обеспечивающей обращение к этой бесконечной памяти.

Важно отметить, что множество программ для этого исполнителя (например, множество машин Тьюринга при фиксированном алфавите входных и выходных данных) счётно.

Поэтому и множество вычислимых функций счётно, в то время как множество функций вида $f\colon N\to N,$ несчётно, даже если $N$ счётно.

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

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

История[править | править код]

Понимание, что часть функций вида $f\colon B^{*}\to B^{*}$ вычислима, а часть нет, появилось ещё до появления первых компьютеров. Теория вычислимости берёт своё начало от диссертации Тьюринга (1936), в которой он ввёл понятие абстрактной вычислительной машины, и функций, вычислимых на ней. По мере развития теории вычислимости было сформулировано несколько определений, которые, как оказалось впоследствии, определяют одно и то же множество функций — множество вычислимых функций: