Построение конечной порождающей системы в группе перестановок, элементарных по Кальмару

Актуальность и цели. Более 30 лет назад на стыке теории рекурсивных функций и теории групп была сформулирована проблема о конечной порождаемости некоторых крупных групп рекурсивных перестановок, связанных с классами иерархии Гжегорчика. Эта проблема была положительно решена С. А. Волковым в 2008 г. Решение С. А. Волкова в техническом плане довольно сложное и использует ряд фактов, доказательство которых потребовало значительных усилий многих математиков. Несмотря на то что этапы полного доказательства по отдельности опубликованы, до сих пор отсутствует автономное изложение, которое не требует обращения к другим утверждениям и источникам. Основной целью работы является воспроизведение всех этапов получения теоремы С. А. Волкова на примере группы перестановок, элементарных по Кальмару. Кроме того, цель заключается также в явном представлении всех перестановок (их число равно 22), которые порождают рассматриваемую группу. Это создает предпосылки для анализа теоретико-числовых, алгебраических и теоретико-рекурсивных свойств перестановок из достаточно широкой и репрезентативной группы перестановок, элементарных по Кальмару. Материалы и методы. В работе используются теоретико-рекурсивные, алгебраические и комбинаторные методы. Результаты и выводы. Описаны (в основном без доказательств) три этапа в получении теоремы С. А. Волкова. При этом удалены все «побочные» результаты, которые возникали при использовании результатов различных авторов. Для первого этапа (построение конечных базисов по суперпозиции в классе K функций, элементарных по Кальмару) рассмотрен весь путь от формулирования проблемы А. Гжегорчиком в 1953 г. до получения «окончательного» результата в 2006 г. Второй этап (построение конечных базисов по суперпозиции в классе всех одноместных функций из K) изложен с доказательствами, специально написанными для настоящей работы. Третий этап (построение конечной порождающей системы в группе $G_K$ всех перестановок из класса K) в основном следует исходной работе С. А. Волкова.