Введение к работе
Актуальность темы. Теория нумераций является в настоящее время сложившейся и интенсивно развивающейся самостоятельной областью математической логики, имеющей многочисленные важные приложения в теории рекурсивных функций, в Computer Science, в вопросах, связанных с разрешимостью элементарных теорий н другими алгоритмическими проблемами алгебраических систем.
Центральными в теории нумераций являются понятие вычислимой нумерации семейства рекурсивно перечислимых (РП) множеств и понятие сводимости нумераций. Эти понятия, а также первые результаты о вычислимых нумерациях появились в работах X. Раиса, В. А, Успенского, X. Роджерса. Основополагающую роль в становлении и развитии проблематики теории нумераций сыграли работы А. И. Мальцева и Ю. Л. Ершова.
В работе [26] X. Роджерс предложил рассматривать вычислимые нумерации с точностью до эквивалентности, т. е. взаимной сводимости, нумераций. Классы эквивалентных вычислимых нумераций семейства Л относительно частичного порядка, индуцируемого отношением сводимости вумеращії, образуют верхнюю лолурешетку 71(Л), называемую в настоящее время полурешеткой Роджерса. Полурешетки Я(Л) определяют алгоритмическую сложность семейств А в целом и, как отмечено Ю. Л. Ершовым [8], во многих вопросах могут быть более полезными, чем различные понятия сложности отдельно взятых элементов этих семейств.
Среди вычислимых нумераций естественным образом выделяются главные и минимальные нумерации, порождающие в полурешетках Роджерса соответственно наибольший и минимальные элементы и играющие в теории вычислимых нумераций ключевую роль. Как правило, проблема определения равенства элементов семейства по их номерам в главной нумерации алгоритмически неразрешима. Нумерации, в которых указанная проблема является алгоритмически разрешимой были названы А. И. Мальцевым [10] разрешимыми. Им же было замечено, что разрешимые нумерации бесконечного семейства эквивалентны однозначным нумерациям и являются минимальными.
Исследование минимальных нумераций начато Р. Фридбергом [22], показавпшм наличие у семейства всех рекурсивно перечислимых мно-
жеств однозначных вычислимых нумераций. В работах М. Б. Пур-Эль, Ю. Л. Ершова, А. Б. Хуторецкого, С. С. Марченкова были построены нервые примеры семейств с различными типами минимальных нумераций: однозначными (разрешимыми), позитивными и неэквивалентными позитивным нумерациями.
Исследование минимальных нумераций проводится в двух основных направлениях — описание семейств, обладающих теми или иными типами минимальных вычислимых нумераций, и выяснение возможного их числа для различных семейств.
Различные достаточные признаки семейств РП множеств, обладающих однозначными вычислимыми нумерациями, получены М. Б. Пур-Эль, А. Лахланом, А. И. Мальцевым, А. Б. Хуторецким, М. Кумме-ром. Описание семейств РП множеств, имеющих позитивные вычислимые нумерации, также продвинуто достаточно далеко в работах А. И. Мальцева, Ю. Л. Ершова, С. С. Марченкова, В. В. Вьюгина, С. А. Бадаева. Вопрос о возможном числе однозначных и позитивных нумерации различных семейств ОРФ и семейств РП множеств исследовался Ю. Л. Ершовым, А. Б. Хуторецким, С. С. Марченко-вым, С. А. Бадаевым, С. С. Гончаровым, и другими авторами.
Минимальные нелозитивиые нумерации, в отличие от однозначных и позитивных, вплоть до недавнего времени были изучены сравнительно слабо. Были известны только три работы [12, 15, 18], в которых рассматривались вопросы о числе минимальных нелозмтивных нумераций некоторых семейств РП множеств. Одной из причин сложившейся ситуации было отсутствие внутреннего описания минимальных нумераций и, вследствие этою, единственный подход к ним, как к нумерациям, порождающим минимальные элементы в полурешетках Роджерса.
В теории вычислимых нумераций хорошо известны две проблемы, поставленные Ю. Л. Ершовым во второй половине шестидесятых годов. Это проблема характеризацни семейств с одноэлементной полурешеткой Роджерса и проблема описания спектра минимальных вычислимых нумераций. Первая проблема решена недавно для случая семейств общерекурсивных функций (ОРФ) С. С. Гончаровым [5] и М. Куимером [24]. Очень важные шаги по решению второй проблемы сделаны С.С.Гончаровым [2] доказавшим, что с точностью до экви-
валентности число однозначных вычислимых нумераций может принимать любое из значений 0,1,2,...,од. Аналогичный результат для позитивных вычислимых нумераций анонсирован им в [5].
Дальнейшее продвижение по обеим этим проблемам обусловлено, на наш взгляд, разработкой новых методов построения минимальных непознтнвных нумераций.
Целью работы является нахождение внутренних критериев минимальности нумераций и разработка конструкций минимальных вычислимых нумераций для
классификации минимальных вычислимых нумераций,
исследования семейств РП множеств как с одноэлементной, так в бесконечной лолурешеткой Роджерса,
исследования спектра минимальных вычислимых нумераций некоторых классических семейств,
решения других проблем, связанных с минимальными нумерациями.
Общая методиха исследования, В диссертации используются методы теории рекурсивных функций и методы теории нумераций.
Научная новизна. В диссертации предложен новый подход к исследованию минимальных нумераций, основанный на их внутренней характеризации, введены новые классы минимальных нумераций и разработаны эффективные методы их построения, позволяющие решить ряд известных проблем.
Практическая и теоретическая ценность. Работа носнт теоретический характер. Ее результаты и методы могут применяться в исследованиях но теории нумераций, теории рекурсивных функций, теории конструктивных моделей, в теоретическом программировании. Результаты диссертации могут быть использованы при чтении специальных курсов и при подготовке монографий.
Апробация результатов диссертации. Результаты диссертационной работы докладывались автором на общегородском семинаре по алгоритмическим проблемам при Алматинском госуниверситете, на семинарах "Алгебра и логика" и "Теория нумераций" Новосибирского госуниверситета, в секционных докладах IX (Ленинград, 1988), X
(Алма-Ата, 19S0) Всесоюзных конференций по математической логике и Ш Международной конференции ио алгебре, посвященной памяти М. И. Каргояолова (Красноярск, 1993), в пленарном докладе на Международной конференции по математической логике, посвященной 85-летию со дня рождения А. К. Мальцева (Новосибирск, 1994).
Публикации. Результаты диссертации опубликованы в работах [27] - [45].
Объем и структура работы. Диссертация изложена на 195 страницах и состоит из введения и 4 глав, рабитых на 11 параграфов. Номера параграфов содержат номер главы, а номера утверждений и определений — номер параграфа. Библиография содержит 99 наименований, включая работы автора по теме диссертации.
Автор выражает глубокую благодарность своему Учителю, Юрию Леонидовичу Ершову, влияние которого предопределило направление его исследований на долгие годы.