РЕКУРСИВНЫЕ ФУНКЦИИ

РЕКУРСИВНЫЕ ФУНКЦИИ — функции y=f( xl, x2, . . ., xn ), значения и аргументы которых суть целые неотрицательные числа и для которых могут быть указаны определенные правила, позволяющие фактически вычислить у по заданному набору xl, x2, . . ., xn , входящему в область определения f. Может быть введено также понятие о частично-рекурсивных функциях, отождествляемых в настоящее время с функциями, вычисляемыми с помощью произвольного алгоритма (см.). Теория рекурсивных функций используется в математической логике (см.) и основаниях математики, а также в теории современных быстродействующих электронных вычислительных машин. Первые работы по рекурсивным функциям были опубликованы немецким математиком Г. Грассманом (XIX в.). Рекурсивные функции интенсивно изучаются после работ немецкого математика Гильберта (20-е годы XX в.). В 1931 г. австрийский математик К. Гёдель доказал с их помощью теорему о невозможности полной аксиоматизации арифметики. Окончательно теория рекурсивных функций становится особой отраслью математики в 40-х годах. Лат. recursio — возвращение.