Российские универсальные энциклопедии
на главную страницу

   
источник статьи:
Большая Советская Энциклопедия
(БСЭ)


Российские универсальные энциклопедии
Брокгауз-Ефрон и Большая Советская Энциклопедия
объединенный словник





Вычислимая функция, одно из основных понятий теории алгоритмов. Функция 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) º х не является вычислимой, если её рассматривать на всей действительной прямой, но является вычислимой, если её рассматривать как функцию натурального или рационального аргумента. В. ф., областью определения которой служит натуральный ряд, называется вычислимой последовательностью.

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









ЭнциклопедиЯ

© gatchina3000.ru, 2001-2012
при использовании материалов сайта, гиперссылка обязательна