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

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

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