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

Вычисли́мая функция — математическая функция, значение которой может быть получено посредством эффективной процедуры — алгоритма. В современной логике вычислимые функции моделируются как частично рекурсивные функции; функции, реализуемые на некоторой машине Тьюринга, машине Поста, регистровой машине; задаваемые нормальным алгоритмом. Эквивалентность классов вычислимых и таким образом моделируемых функций постулируется тезисом Чёрча — Тьюринга (или его аналогами).

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

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

$N=B^{*}\cup \{\mathrm{\top }\}$,

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

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

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

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

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

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

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

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

Исследования о возможности физического вычисления функций, не удовлетворяющих современным моделям вычислимости, объединены в направление, обозначаемое как сверхтьюринговые вычисления.

Литература

• Шаблон:Книга

Ссылки

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