Том 16, номер 2, 2009 г., Стр. 42-60
УДК 519.712
С. А. Волков
О классе функций, элементарных по Сколему
Аннотация:
Рассматриваются различные эквивалентные определения класса функций, элементарных по Сколему (аналогичные известным для класса функций, элементарных по Кальмару), и некоторые результаты, связанные с этим классом, полученные различными математиками. Некоторые определения данного класса исследовались математиками независимо друг от друга, и в работе доказана их эквивалентность. Исследуется вопрос о наличии в этом классе конечных базисов по суперпозиции. Доказывается, что проблема наличия таких базисов эквивалентна известной проблеме из теории сложности вычислений.
Библиогр. 26.
Ключевые слова: классификация рекурсивных функций, вычислительная сложность.
Волков Сергей Александрович 1
1. Московский государственный университет им. М. В. Ломоносова,
Воробьёвы горы, 119992 Москва, Россия
Статья поступила 24 октября 2008 г.
