Частково рекурсивні функції
Зміст
Основні визначення [ред.]
| Визначення: |
| Частково рекурсивними(англ.partial recursive) називають функції, які можна отримати за допомогою правил мінімізації, підстановки та рекурсії з константної функції [math] \textbf 0 [/math] , функції [ math] I(x) = x + 1, [/math] і набору функцій [math] P_(x_1,\ldots,x_n) = x_k,[/math] де [math] k \leqslant n [/math] . |
Зауважимо, що частково рекурсивна функція може бути не визначена для деяких значень аргументів.
| Визначення: |
| Загальнорекурсивними(англ.general recursive) називають всюди певні частково рекурсивні функції. |
Будь-яка примітивно-рекурсивна функція є загальнорекурсивною. Тому і для частково рекурсивних функцій можна вважати, що у них як аргумент і результат можуть бути списки з натуральних чисел.
Обчислювані та частково рекурсивні функції [ред.]
Програма, що обчислює частково рекурсивну функцію, легко пишеться будь-якою мовою програмування. Тому нам достатньо показати що будь-яка функція, що обчислюється, примітивно рекурсивна. Функції [math] IN [/math] , [math] OUT [/math] , [math] N [/math] , і як видається стан машини Тюрінга описано в доказі теореми про примітивну рекурсивність обчислюваних функцій. Функція [math] \mathrm[/math] повертає мінімальне число кроків, за яке програма обчислює нашу функцію потрапить у стан [math] \mathrm [/math] . Покажемо, що вона частково рекурсивна. [math] \mathrm [/math] , де [math] p_i [/math] - взяття [math]i[/math] - того елемента списку. Операціїпорівняння тут реалізовані також як і примітивно рекурсивних функціях,але якщо рівність виконується то функція перевірки на рівність повертає [math] 0 [/math] , інакше [math] 1 [/math] .
У результаті [math] \ mathrm [/ Math] - частково рекурсивна функція.
З цієї теореми і нерозв'язності мови програм, що завершуються при будь-якому вході, випливає алгоритмічна нерозв'язність проврк, і частково рекурсивної функції на загальнорекурсивність.
Зв'язок між загальнорекурсивними та примітивно рекурсивними функціями [ред.]
Кожна примітивна рекурсивна функція відповідає її опису, не обов'язково єдина. Воно складається з послідовних визначень функцій через попередні, закінчуючи нашою функцією. При цьому варто зауважити, що в описі не буде перехресної рекурсії, оскільки за визначенням примітивно-рекурсивної функції вона повинна бути отримана з базових примітивів за кінцеве число кроків.
Безліч описів одномісних примітивно рекурсивних функцій можна розв'язати, отже всі описи можна занумерувати (описи можуть містити і [math] n [/math] місцеві функції як проміжні). За описом примітивно рекурсивної функції та значенням аргументу її можна обчислити передавши функцію разом із аргументом у відповідний інтерпретатор.