Статья в сборнике "Математические вопросы кибернетики" №3, Москва, 1991
Авторы:Марченков С.С.
Базисы по суперпозиции в классах рекурсивных функций
Аннотация:
В обзоре представлены основные методы построения базисов по суперпозиции (конечных и бесконечных) в классах всюду определенных функций. В терминах максимально универсальных функций установлен критерий существования конечных базисов в □2-замкнутых классах. Приведены различные примеры конечных базисов в классе функций, элементарных по Кальмару. Доказано, что всякий счетный примитивно-рекурсивно замкнутый класс имеет бесконечный базис по суперпозиции. Получены общие теоремы, связывающие существование базисов по суперпозиции в классах многоместных и одноместных функций.
Ключевые слова:
базисы по суперпозиции, классы рекурсивных функций