Рекурсивні функції

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

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

Поняття рекурсивних функцій

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

нульова функція $\ O^{n}(x_{1},\dots ,x_{n})=0$
функція слідування $\ s(x)=x+1$
функція проектування $\ 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})$ не визначено, якщо:

значення $f(x_{1},\dots ,x_{n-1},\alpha )$ визначено для всіх $y<\alpha$ , але відмінні від $x_{n}$ , а значення $f(x_{1},\dots ,x_{n-1},\alpha )$ не визначено (α = 0, 1, 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);

Джерела інформації

Енциклопедія кібернетики, т. 2, с. 290–292. (не повністю).

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.