Загальна рекурсивна функція

Загальні рекурсивні функції, часткові рекурсивні функції, μ-рекурсивні функції — в математиці, це часткові функції з натуральних чисел в натуральні числа, введені як уточнення класу обчисленних функцій. Загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій. У зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу, в математичній логіці, основах математики та кібернетиці, як ефективно обчислювані функції. Тільки такі функції можна обчислювати на електронних обчислювальних машинах та інших цифрових пристроях.

При введенні класу ефективно обчислюваних функцій природним чином виникає питання уточнення конструктивних об'єктів, на яких визначено ці функції. Клас всіх таких об'єктів широкий. В той же час, з допомогою методу арифметизації, запропонованого австрійським математиком Куртом Геделем, всі такі об'єкти легко зводяться до натуральних чисел. Перенесення понять і методів вироблених в теорії рекурсивних функцій на функції визначені на складніших конструктивних областях (множини слів деякого алфавіту, формул деякої теорії, графів тощо) не створює принципових ускладнень.

Визначення

Базовими примітивними функціями, за визначенням, є:

1. нульова функція $\ O^{n}(x_{1},\dots ,x_{n})=0$
2. функція наступності $\ s(x)=x+1$
3. функція проектування $\ I_{m}^{n}(x_{1},\dots ,x_{n})=x_{m}$

Операція суперпозиції

Кажуть, що функція $g(x_{1},\dots ,x_{m})$ виникає із функцій $f(x_{1},\dots ,x_{n})$, $f_{1}(x_{1},\dots ,x_{m})$, …, $f_{n}(x_{1},\dots ,x_{m})$ суперпозицією, якщо

$\ g(x_{1},\dots ,x_{m})=f{\Big (}f_{1}(x_{1},\dots ,x_{m}),\dots ,f_{n}(x_{1},\dots ,x_{m}){\Big )}$

Операція примітивної рекурсії

Функція $\ f(x_{1},\dots ,x_{n+1})$ утворюється із функцій $\ g(x_{1},\dots ,x_{n}),\;h(x_{1},\dots ,x_{n+2})$ за допомогою примітивної рекурсії, якщо для всіх натуральних значень $\ x_{1},\dots ,x_{n},y$ маємо

$\ f(x_{1},\dots ,x_{n},0)=g(x_{1},\dots ,x_{n});$

$\ f(x_{1},\dots ,x_{n},y+1)=h{\Big (}x_{1},\dots ,x_{n},y,f(x_{1},\dots ,x_{n},y){\Big )}.$

Операція мінімізації

Позначимо через $\mu y(f(x_{1},\dots ,x_{n-1},y)=x_{n})$ найменше значення $\alpha$, для якого $f(x_{1},\dots ,x_{n-1},\alpha )=x_{n}$. Будемо вважати, що $\mu y(f(x_{1},\dots ,x_{n-1},y)=x_{n})$ не визначено, якщо:

1. значення $f(x_{1},\dots ,x_{n-1},\alpha )$ визначено для всіх $y<\alpha$, але відмінні від $x_{n}$, а значення $f(x_{1},\dots ,x_{n-1},\alpha )$ не визначено (α = 0, 1, 2, …) або
2. значення $f(x_{1},\dots ,x_{n-1},\alpha )$ визначені для всіх α = 0, 1, 2, … та відмінні від $x_{n}$.

Таким чином, значення $\mu y(f(x_{1},\dots ,x_{n-1},y)=x_{n})$ є функцією $g(x_{1},\dots ,x_{n})$ від змінних $x_{1},\dots ,x_{n}$. Кажуть, що ця функція отримана від функції $f(x_{1},\dots ,x_{n-1},y)$ із допомогою мінімізації.

Примітивно рекурсивна функція

Функція називається примітивно рекурсивною, якщо її можна отримати із функцій $\ s(x)$, $\ O^{n}(x_{1},\dots ,x_{n})$ та $\ I_{m}^{n}(x_{1},\dots ,x_{n})$ скінченною кількістю операцій суперпозиції та примітивної рекурсії.

Частково рекурсивна функція

Функція називається частково рекурсивною, якщо отримана із вказаних функцій застосуванням скінченної кількості операцій суперпозиції, примітивної рекурсії та мінімізації. Всюди визначена частково рекурсивна функція називається загальнорекурсивною.

Одним з популярних прикладів загальнорекурсивної, але не примітивно рекурсивної функції є функція Акермана.

Дослідження рекурсивних функцій

Рекурсивні функції, виступаючи як еквівалент поняття ефективно рекурсивних функцій з моменту їх введення піддавались інтенсивному дослідженню.

Перш за все, в класі рекурсивних функцій були виділені та вивчені підкласи простіших функцій — примітивно рекурсивних, елементарних за Л. Кальмару. Доведено, що клас загальнорекурсивних функцій ширший класу примітивно рекурсивний: існують загальнорекурсивні функції, що не є примітивно рекурсивними. Очевидно, що клас частково ширший класу загальнорекурсивних функцій.

Доведено, також, що будь-яка частково рекурсивна функція може бути представлена у вигляді:

$g(x_{1},\dots ,x_{s})=\phi (\mu z(f(x_{1},\dots ,x_{s},z)=0))$,

Де $\phi$ і $f$ — примітивно рекурсивні функції, тобто, для отримання будь-якої частково рекурсивної функції оператор μ можна застосувати не більше одного разу.

Робились спроби класифікації рекурсивних функцій. Ієрархія Гжегорчика примітивно рекурсивних функцій польського математика А. Гжегорчика, а класифікацію, основану на понятті звідності (в теорії алгоритмів), виконав американський математик Е. Пост.

Алгебри рекурсивних функцій

Також досліджувались алгебри рекурсивних функцій: на множині рекурсивних функцій визначались ті чи інші операції, відносно яких множини функцій утворювали універсальні алгебри. Як такі операції обирались операції суперпозиції (*), додавання (+) а також операція обернення $f^{-1}$ визначена схемою $f^{-1}(x)=\mu y(f(y)=x)$, та операція ітерації i, що визначається схемою $g(0)=0$, $g(x+1)=f(g(x))$. Нехай $s(x)=x+1$,

$g(x)={\begin{cases}x-[{\sqrt {x}}]^{2},\\0,\end{cases}}$	якщо $x>[{\sqrt {x}}]^{2};$
	інакше

де функція [α] означає максимальне ціле число, не більше за α.

Доведено, що всі одномісні примітивно рекурсивні функції, і лише вони можуть бути отримані із функцій $s(x)$, $g(x)$ скінченною кількістю операцій додавання, суперпозиції та ітерації.

Аналогічно, кожну загальнорекурсивну функцію можна отримати із функцій $s(x)$, $g(x)$ скінченною кількістю операцій додавання суперпозиції та обернення, при чому останню виконують лише тоді, коли її результатом є всюди визначена функція. Якщо зняти це обмеження, тоді можна отримати всі одномісні частково рекурсивні функції.

Головним чином, досліджувались три алгебри:

• ${\mathfrak {A}}_{pr}=\langle F_{pr},+,*,i\rangle$
• ${\mathfrak {A}}_{cr}=\langle F_{cr},+,*,{}^{-1}\rangle$
• ${\mathfrak {A}}_{gr}=\langle F_{gr},+,*,{}^{-1}\rangle$

де $F_{pr}$, $F_{cr}$ та $F_{gr}$ — множини всіх одномісних примітивно рекурсивних, частково рекурсивних та загальнорекурсивних функцій. Досліджувались найприродніші питання: наявність скінченних базисів, приклади підалгебр, описання максимальних підалгебр, тобто, таких підалгебр, які не містяться в жодних інших підалгебрах самих алгебр, ізоморфізми та автоморфізми підалгебр, конгруенції на підалгебрах, питання скінченної визначеності алгебри тощо.

Разом із дослідженням рекурсивних функцій, широко досліджуються рекурсивні предикати і пов'язані з ними множини — підмножини множини натуральних чисел.

Рекурсивні функції в програмуванні

Базисний приклад в мові PHP: При створенні нової функції f() в її тілі викликається та сама функція f() зі зміненим аргументом:

function f($x){

	# Обчислення та друк добутку числа на 2.
	return $x*2;
	$y=$x*2;
	
	# Виклик функції f() в власному тілі ще раз, але з новим аргументом.
	f($y);
}

# Приклад 1: Отримуємо числа добуток 1*2 яких ще раз перемножувався на 2:
# 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 і т.д.
print f(1);

# Приклад 2: Отримуємо числа добуток 3*2 яких ще раз перемножувався на 3:
# 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144 і т.д.
print f(3);

Див. також

• Теза Черча
• Рекурсія
• Теорія обчислюваності
• Універсальні рекурсивні функції

Література

• (укр.) Гаврилків В. М. Формальні мови та алгоритмічні моделі. — І.-Ф.  : Голіней, 2023. — 180 с.
• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973. — Т. 2. — С. 290–292.
• Роджерс Х.. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)