Общая рекурсивная функция
-
Определение и свойства μ-рекурсии
- μ-рекурсия — это форма рекурсии, которая позволяет определить функцию, используя только μ-оператор.
- μ-оператор — это оператор, который минимизирует функцию, применяя ее к каждому аргументу.
- μ-рекурсивные функции могут быть определены с использованием только примитивно-рекурсивных функций и μ-оператора.
-
Примеры μ-рекурсивных функций
- Примеры включают определение квадратного корня и функции, которые не могут быть определены без μ-оператора.
- μ-рекурсивные функции могут быть использованы для определения функций, которые не являются примитивно-рекурсивными.
-
Теорема о нормальной форме и ее следствия
- Клини доказал, что для каждой μ-рекурсивной функции существует примитивно-рекурсивная функция, индекс которой определяет эту функцию.
- Это позволяет определить μ-рекурсивные функции с помощью единственного экземпляра μ-оператора.
-
Символизм в теории рекурсии
- В литературе используются различные символические обозначения для упрощения записи рекурсивных функций.
- Примеры включают использование различных символов для обозначения константы, функции преемника, функции идентификации и оператора композиции.
-
Примеры использования μ-рекурсии
- Примеры включают вычисление числа Фибоначчи и функции McCarthy 91.
-
Дополнительные ресурсы
- Статья в Стэнфордской энциклопедии философии предоставляет дополнительную информацию и ссылки.
- Компилятор для преобразования рекурсивных функций в эквивалентные машины Тьюринга доступен для использования.