Рекурсивна функція (теорія обчислюваності)
Термінрекурсивна функціяв теорії обчислюваності використовується для позначення трьох класів функцій:
Останні збігаються з класом обчислюваних за Тьюрингом функцій. Визначення цих трьох класів дуже пов'язані. Вони запроваджено Куртом Геделем з метою формалізації поняття обчислюваності.
Безліч частково рекурсивних функцій включає безліч загальнорекурсивних функцій, а загальнорекурсивні функції включають примітивно рекурсивні функції. Частково рекурсивні функції іноді називають просто рекурсивними функціями.
Зміст
Визначення
Визначення поняттяпримітивно-рекурсивної функціїє індуктивним. Воно складається із вказівки класу базових примітивно рекурсивних функцій та двох операторів (суперпозиціїтапримітивної рекурсії), що дозволяють будувати нові примітивно рекурсивні функції на основі вже наявних.
До базових примітивно рекурсивних функцій відносяться функції наступних трьох видів:
Оператори підстановки та примітивної рекурсії визначаються таким чином:
Безлічпримітивно рекурсивних функцій— це мінімальна множина, що містить усі базові функції та замкнене щодо зазначених операторів підстановки та примітивної рекурсії.
У термінах імперативного програмування — примітивно рекурсивні функції відповідають програмним блокам, у яких використовується лише арифметичні операції, і навіть умовний оператор і оператор арифметичного циклу (оператор циклу, у якому число ітерацій відоме на момент початку циклу). Якщо програміст починає використовувати оператор циклу while , у якому число ітерацій заздалегідь невідомо і, у принципі, може бути нескінченним, він перетворюється на клас частково рекурсивних функций.
Вкажемо наряд широко відомих арифметичних функцій, що є примітивно рекурсивними.
Частково рекурсивна функціявизначається аналогічно примітивно рекурсивною, тільки до двох операторів суперпозиції та примітивної рекурсії додається ще третій оператор - мінімізації аргументу.
Частково рекурсивні функції для деяких значень аргументу можуть бути не визначені, так як оператор мінімізації аргументу не завжди коректно визначено, оскільки функція f може бути не рівною нулю за жодних значень аргументів. З погляду імперативного програмування, результатом частково рекурсивної функції може бути як число, а й виняток чи відхід у нескінченний цикл, відповідні невизначеному значенню.
Загальнорекурсивна функція- частково рекурсивна функція, визначена для всіх значень аргументів. Завдання визначення того, є частково рекурсивна функція з даним описом загальнорекурсивної чи ні, алгоритмічно нерозв'язна.
Легко зрозуміти, що будь-яка примітивно рекурсивна функція є частково рекурсивною, оскільки за визначенням оператори для побудови частково рекурсивних функцій включають оператори для побудови примітивно рекурсивних функцій.
Також зрозуміло, що примітивно рекурсивна функція визначена скрізь і тому є загальнорекурсивною функцією (примітивно рекурсивна функція не має приводу «зависати», тому що при її побудові використовуються оператори, що визначають скрізь певні функції).
Досить складно довести існування та навести приклад загальнорекурсивної функції, яка не є примітивно рекурсивною. Одним із популярних прикладів є функція Аккермана. Інший приклад загальнорекурсивної функції, яка не є примітивно рекурсивною, будується діагональним методомКантора з універсальної функції для множини одномісних примітивно рекурсивних функцій.
Як було показано Гёделем, частково рекурсивні функції збігаються з безліччю функцій, що обчислюються. [джерело не вказано 2563 дні]
Терміни «частково рекурсивна функція» та «загальнорекурсивна функція» прижилися в силу історичних причин і по суті є результатом неточного перекладу англійських термінівpartial recursive functionтаtotal recursive function, які за змістом більш правильно перекладати як «рекурсивні функції, визначені на частині множини можливих аргументів» і «рекурсивні функції, визначені на всій множині можливих аргументів». Прислівник «частково» відноситься не до прикметника «рекурсивні», а до області визначення функції. Можливо, правильнішою назвою було б «частково певні рекурсивні функції» і просто «скрізь певні рекурсивні функції». Але довгі назви не прижилися.