Вычисли́мые фу́нкции — множество функций то есть отображения множества натуральных чисел во множество натуральных чисел, в математических обозначениях это ${\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 ), в которой он ввёл понятие абстрактной вычислительной машины, и функций, вычислимых на ней. По мере развития теории вычислимости было сформулировано несколько определений, которые, как оказалось впоследствии, определяют одно и то же множество функций — множество вычислимых функций:

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

См. также

Примечания

Ссылки

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