начальный
-
Определение и классификация элементарных рекурсивных функций
- Элементарные рекурсивные функции — это объединение классов примитивных рекурсивных функций.
- Название «элементарные» было предложено Ласло Кальмаром и относится к неразрешимости многих задач.
- Существуют примитивно-рекурсивные функции, которые не являются элементарными.
-
Основные свойства и примеры элементарных рекурсивных функций
- Основные функции включают нулевую функцию, функцию-преемницу и проекционные функции.
- Композиция элементарных рекурсивных функций является элементарной рекурсивной функцией.
- Ограниченное суммирование и ограниченное произведение также являются элементарными рекурсивными функциями.
-
Основы и младшие элементарные рекурсивные функции
- Элементарные функции совпадают с замыканием по проекциям и некоторым другим функциям.
- Младшие элементарные рекурсивные функции отличаются от элементарных отсутствием ограниченного произведения.
- Младшие элементарные рекурсивные функции известны как элементарные функции Сколема и имеют полиномиальный рост.
-
Описательная характеристика и связь с другими классами сложности
- Элементарные рекурсивные функции равны классу HO языков, описываемых формулами логики высшего порядка.
- Элементарные рекурсивные функции связаны с арифметикой элементарных функций и иерархией Гжегорчика.
-
Рекомендации и дополнительная литература
- Статья основана на книге Роуз, Х.Э. «Субрекурсия: функции и иерархии».
Полный текст статьи: