Что значит "вычислимая функция"

одно из основных понятий теории алгоритмов. Функция f называется вычислимой, если существует алгоритм , перерабатывающий всякий объект х, для которого определена функция f, в объект f (x) и не применимый ни к какому x, для которого f не определена. Примеры: х ≈ натуральное число, f (x) = х2; x ≈ пара рациональных чисел x1 и x2, f (x) = x1: x2 (эта функция определена лишь для тех x, у которых x2 ¹0); X ≈ пара матриц X1 и X2 с целочисленными элементами, f (X) = X1X2 (эта функция определена лишь для тех X, у которых число стоблцов в X1 совпадает с числом строк в X2). Аргументами и значениями В. ф. могут быть лишь так называемые конструктивные объекты (см. Конструктивное направление в математике) (ибо лишь с такими объектами могут оперировать алгоритмы); таким образом, функция f такая, что f (x) º х не является вычислимой, если её рассматривать на всей действительной прямой, но является вычислимой, если её рассматривать как функцию натурального или рационального аргумента. В. ф., областью определения которой служит натуральный ряд, называется вычислимой последовательностью.

В. А. Успенский.

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

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

N = B ∪ {undef}, 

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

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

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

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