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

ВЫЧИСЛИМАЯ ФУНКЦИЯ — одно из основных понятий теории алгоритмов (см. Алгоритмов теория). Функция  называется вычислимой, если существует алгоритм, перерабатывающий в  всякий , для которого  определена, и не применимый ни к какому , для которого  не определена. Значениями аргумента и значениями В. ф. могут быть лишь так называемые конструктивные объекты.

Примеры. Для  функция  будет В. ф. Эта же функция для  не будет В. ф. (ввиду неконструктивности задания аргумента). Саррюса правилом задается В. ф. на множестве квадратных матриц третьего порядка с натуральными, целыми или рациональными элементами.