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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

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

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

История[править | править исходный текст]

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

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]