ВЫЧИСЛИМАЯ ФУНКЦИЯ

ВЫЧИСЛИМАЯ ФУНКЦИЯ, одно из основных понятий теории алгоритмов. Функция f наз. вычислимой, если существует алгоритм, перерабатывающий всякий объект х, для к-рого определена функция f, в объект f(x) и не применимый ни к какому х, для к-рого f не определена. Примеры: х - натуральное число, f (х) = х²; х - пара рациональных чисел x₁ и x₂, f(x) = х₁: Х₂(эта функция определена лишь для тех х, у к-рых х₂ не равно 0); X - пара матриц X₁ и Х₂ с целочисленными элементами, f(X) = = X₁X₂ (эта функция определена лишь для тех X, у к-рых число столбцов в X, совпадает с числом строк в Х₂). Аргументами и значениями В. ф. могут быть лишь т. н. конструктивные объекты (см. Конструктивное направление в математике) (ибо лишь с такими объектами могут оперировать алгоритмы); т. о., функция f такая, что f(х) = x: не является вычислимой, если её рассматривать на всей действительной прямой, но является вычислимой, если её рассматривать как функцию натурального или рационального аргумента. В. ф., областью определения к-рой служит натуральный ряд, наз. вычислимой последовательностью.

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