Рекурсивні функції (від позднелатінського recursio — повернення), назва, що закріпилася за одним з найбільш поширених варіантів уточнення загального поняття арифметичного алгоритму, тобто такого алгоритму, допустимими вихідними даними якого є системи натуральних чисел, а можливі результати вживання є натуральними числами. Р. ф. були введені у 30-х рр. 20 ст С. До. Кліні, що у свою чергу грунтувався на дослідженнях До. Геделя, Же. Ербрану і ін. математиків.
Кожен Р. ф. задається кінцевою системою рівності точно охарактеризованого типа в тому сенсі, що її значення обчислюються з допомогою цієї системи рівності по точно формульованих правилах, причому таким чином, що у результаті для обчислення значень заданим Р. ф. виходить алгоритм певного типа.
Арифметичні функції, для обчислення значень яких є які-небудь алгоритми, прийнято називати обчислюваними. Обчислювані функції грають в математиці важливу роль. В той же час, якщо поняттю алгоритму тут не буде доданий точний сенс, то і само поняття обчислюваної функції виявиться декілька розпливчатим. Р. ф. вже через сам характер свого визначення виявляються обчислюваними. У відомому сенсі вірно і зворотне: є серйозні підстави вважати, що математичне по своєму характеру поняття рекурсивності є точним еквівалентом декілька розпливчатого поняття вичислімості. Пропозиція вважати поняття вичислімості співпадаючим за об'ємом з поняттям рекурсивності відома в теорії Р. ф. під назвою тези Черча по імені американського математика А. Черча, що вперше (у 30-х рр. 20 ст) сформулював і обгрунтував це пропозиція. Прийняття тези Черча дозволяє додати поняттю обчислюваної арифметичної функції точний математичний сенс і піддати це поняття вивченню за допомогою точних методів.
Р. ф. є частковими функціями, тобто функціями, не обов'язково усюди визначеними. Щоб підкреслити цю обставину, часто як синонім використовують термін «частково рекурсивні функції». Р. ф., визначені при будь-яких значеннях аргументів, називають загальнорекурсивними функціями.
Визначенню Р. ф. може бути додана наступна форма. Фіксується невелике число надзвичайно простих вихідних функцій, що обчислюються в згаданому вище інтуїтивному сенсі (функція, тотожно рівна нулю, функція збільшення одиниці і функції, що виділяють з системи натуральних чисел член з даним номером); фіксується невелике число операцій над функціями, що переводять обчислювані функції знову в обчислюваних (оператори підстановки, примітивної рекурсії і мінімізації). Тоді Р. ф. визначаються як такі функції, які можна отримати з початкових в результаті кінцевого числа вживань згаданих вище операцій.
Оператор підстановки зіставляє функції f від n змінних і функціям g 1 . . ., g n від m змінних функцію h від m змінних таку, що для будь-яких натуральних чисел x 1 , .., x m
h ( x 1 , .., x m ) @ f ( g 1 ( x 1 , .., x m ) ..., g m ( x 1 , .., x m ))
(тут і нижче умовна рівність @ означає, що обидва вираження, що зв'язуються їм, осмислено одночасно і в разі свідомості мають одне і те ж значення).
Оператор примітивної рекурсії зіставляє функціям f від n змінних і g від n + 2 змінних функцію h від n + 1 змінних таку, що для будь-яких натуральних чисел x 1 , .. .., x n , в
h ( x 1 , .., x n ,0) @ f ( x 1 , .., x n ),
h ( x 1 , .., x n , в + 1) @ g ( x 1 , .., x n , в , h ( x 1 , .., x n , в )).
Оператор мінімізації зіставляє функції f від n змінних функцію h від n змінних таку, що для будь-яких натуральних чисел x 1 , .., x n
h ( x 1 , .., x n ) @ f ( x 1 , .., x n-1 , в )
де в таке, що f ( x 1 , .., x n-1 , в -1) визначені і відмінні від x n , а f ( x 1 , .., x n , в ) визначена і рівна x n , якщо ж в з вказаними властивостями не існує, то значення h ( x 1 , .., x n ) вважається не визначеним.
Важливу роль в теорії Р. ф. грають т.з. примітивно рекурсивні функції — Р. ф., що виходять з вихідних функцій в результаті кінцевого числа вживань одних лише операторів підстановки і примітивної рекурсії. Вони утворюють власну частину класу загальнорекурсивних функцій. Через відому теорему Кліні про нормальну форму Р. ф. можуть бути вказані такі конкретні примітивно рекурсивні функції U від однієї змінної і T n от n + 2 змінних, що для будь-якого Р. ф. j від n змінних і для будь-яких натуральних чисел x 1 . . ., x n має місце рівність j( x 1 ..., x n )@ U ( в ), де в є найменше з чисел z таких, що T n (j, x 1 ..., x n , z ) = 0 (тут j є т.з. гедельов номер функції j — число, яке ефективно будується за системою рівності, задаючою функцію j). З цієї теореми, зокрема, витікає, що для Р. ф. від п змінних може бути побудована універсальний Р. ф. від n +1 змінних, тобто такий Р. ф. Ф n , що для будь-якого Р. ф. j від n змінних і для будь-яких натуральних чисел x 1 . . ., x n має місце умовна рівність
j( x 1 . . ., x n )@ Ф n (, x 1 . . ., x n ).
Це — один з центральних результатів загальної теорії Р. ф.
Теорія Р. ф., будучи частиною алгоритмів теорії, є розгалуженою математичною дисципліною з власною проблематикою і з додатками в ін. розділах математики. Поняття «Р. ф.» може бути покладене в основу конструктивного визначення вихідних математичних понять. Широке вживання теорія Р. ф. знайшла в математичній логіці . Зокрема, поняття примітивне рекурсивній функції лежить в основі первинного доведення знаменитої теореми Геделя про неповноту формальної арифметики, а поняття «Р. ф.» в його повному об'ємі було використано С. К. Кліні для інтерпретації інтуїционістськой арифметики (дослідження це склало цілу епоху в області семантики ). Апарат теорії Р. ф. використовується також в теорії обчислювальних машин і програмування.
Дослідження показали, що всі відомі уточнення загального поняття алгоритму, у тому числі Р. ф., взаємно моделюють один одного і, отже, ведуть до одного і того ж поняття обчислюваної функції. Ця обставина служить серйозним аргументом на користь тези Черча.
Літ.: Кліні С. До., Введення в математику. пер.(переведення) з англ.(англійський), М., 1957; Успенське Ст А., Лекції про обчислювані функції, М., 1960; Мальцев А. І., Алгоритми і рекурсивні функції, М., 1965; Роджерс Х., Теорія рекурсивних функцій і ефективна вичислімость, пер.(переведення) з англ.(англійський), М., 1972.
