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

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

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