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

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

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

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

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

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

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

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

История

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

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

См. также

• Тезис Чёрча — Тьюринга
• Полнота по Тьюрингу
• Частично рекурсивные функции
• Общерекурсивные функции
• Примитивно рекурсивные функции
• Разрешимые множества
• Перечислимые множества
• Невычислимые функции (алгоритмически неразрешимые проблемы):

• Проблема остановки
• Проблема эквивалентности алгоритмов
• Проблема доказательства верности или неверности утверждения
• Десятая проблема Гильберта — разрешимость диофантова уравнения в целых числах
• Самоприменимость

Ссылки

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