Рекурсивні функції: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Олюсь (обговорення | внесок) мНемає опису редагування |
Олюсь (обговорення | внесок) мНемає опису редагування |
||
Рядок 6:
== Поняття рекурсивних функцій ==
Базовими примітивними функціями, за визначенням, є:
Рядок 30 ⟶ 28:
Таким чином, значення <math>\mu y(f(x_1, \dots, x_{n-1}, y) = x_n)</math> є функцією <math>g(x_1, \dots, x_n)</math> від змінних <math>x_1, \dots, x_n</math>. Кажуть, що ця функція отримана від функції <math>f(x_1, \dots, x_{n-1}, y)</math> із допомогою ''мінімізації''.
=== Примітивно рекурсивна функція ===
Функція називається '''примітивно рекурсивною''', якщо її можна отримати із функцій <math>\ s(x)</math>, <math>\ O^n(x_1, \dots, x_n)</math> та <math>\ I^n_m(x_1, \dots, x_n)</math> скінченною кількістю операцій суперпозиції та примітивної рекурсії
=== Функція називається '''частково рекурсивною''', якщо отримана із вказаних функцій застосуванням скінченної кількості операцій суперпозиції, примітивної рекурсії та мінімізації. Всюди визначена частково рекурсивна функція називається ''загальнорекурсивною''. == Дослідження рекурсивних функцій ==
| |||