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

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

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

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

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

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

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

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

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

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

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

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

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

История

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

• функции, реализуемые на машинах Тьюринга (Алан Тьюринг);
• функции, реализуемые на нормальных алгоритмах Маркова (А. А. Марков);
• функции, реализуемые на машине Поста;
• частично рекурсивные функции (Курт Гёдель, Стивен Клини);
• функции, реализуемые на регистровой машине.

См. также

Примечания

Ссылки

• Курсы по теории вычислимости

Эта страница в последний раз была отредактирована 18 сентября 2023 в 21:05.