Минимальные нумерации тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

Спар!авизированный совет Д 002.23.01

На правах рухописи рг5 0д УДК 510.57

1 5 ДЕК 139В

БАДАЕВ Серяжжан Агаб&евич МИНИМАЛЬНЫЕ НУМЕРАЦИИ 01.01.06 — натематнческ&я логика, алгебра и теория чисел

Автореферат диссертация на соискание ученой степени доктора фязнхо- натематячесзпгх наук

Научный консультант академик РАН, профессор Ю.Л.Ершов

Новосибирск -1996

Работа выполнена в Институте теоретической в прикладно математики Национальной академии наук Республики Казю стан

Официальнне оппоненты:

доктор физиЕо-математическюс наук, профессор В.П.Добрица доктор физико-математических наук, профессор А.О.Морозов доктор физико-математических наук (профессор В.Л.Селкванс

Ведущая организация — Казанский государственный

университет

Защита состоится " М. 1996 г. в ^ часов г

заседании Специализированного совета Д 002.23.01 при Инея туте математики СЮ РАН по адресу: 630090, Новосибирск, 9 Университетский проспект, 4

С диссертацией можно ознакомиться в библиотеке Институт математики СО РАН.

Автореферат разослан * 1996 г.

Ученый секретарь Специализированною совета канд. физ.-мат. наук

С. Т. Федор»

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Теория нумераций является в настоящее время сложившейся и интенсивно развивающейся самостоятельной областью математической логики, имеющей многочисленные важные приложения в теории рекурсивных функций, в Computer Science, в вопросах, связанных с разрешимостью элементарных теорий и другими алгоритмическими проблемами алгебраических систем.

Центральными в теории нумераций являются понятие вычислимой нумерации семейства рекурсивно перечислимых (РП) множеств и понятие сводимости нумераций. Эти понятия, а также первые результаты о вычислимых нумерациях появились в работах X. Райса, В. А, Успенского, X. Роджерса. Основополагающую роль в становлении и развитии проблематики теории нумераций сыграли работы А. И. Мальцева и Ю. JT. Ершова.

В работе [26] X. Роджерс предложил рассматривать вычислимые нумерации с точностью до эквивалентности, т. е. взаимной сводимости, нумераций. Классы эквивалентных вычислимых нумераций семейства Л относительно частичного порядка, индуцируемого отношением сводимости нумераций, образуют верхнюю лолурвтетку И(Л)} называемую в настоящее время полурешеткой Роджерса. Полурешетки 71(Л) определяют алгоритмическую сложность семейств А в целом и, как отмечено Ю. Л. Ершовым [8], во многих вопросах могут быть более полезными, чем различные понятия сложности отдельно взятых элементов этих семейств.

Среди вычислимых нумераций естественным образом выделяются главные и минимальные нумерации, порождающие в полурешетках Роджерса соответственно наибольший и минимальные элементы и играющие в теории вычислимых нумераций ключевую роль. Как правило, проблема определения равенства элементов семейства по их номерам в главной нумерации алгоритмически неразрешима. Нумерации, в которых указанная проблема является алгоритмически разрешимой были названы А. И. Мальцевым [10] разрешимыми. Им же было замечено, что разрешимые нумерации бесконечного семейства эквивалентны однозначным нумерациям и являются минимальными.

Исследование минимальных нумераций начато Р. Фридбергом [22], показавшим наличие у семейства всех рекурсивно перечислимых мно-

жеств однозначных вычислимых нумераций. В работах М. Б. Пур-Эль, Ю. Л. Ершова., А. Б. Хуторецкош, С. С. Марченкова были построены первые примеры семейств с различными типам« минимальных нумераций: однозначными (разрешимыми), позитивными и неэквивалентными позитивным нумерациями.

Исследование минимальных нумераций проводится в двух основных направлениях — описание семейств, обладающих теми или иными типами минимальных вычислимых нумераций, и выяснение возможного их числа для различных семейств.

Различные достаточные признаки семейств РП множеств, обладающих однозначными вычислимыми нумерациями, получены М. Б. Пур-Эль, А. Лахланом, А. И. Мальцевым, А. Б. Хуторецким, М. Кумме-ром. Описание семейств РП множеств, имеющих позитивные вычислимые нумерации, также продвинуто достаточно далеко в работах А. И. Мальцева, Ю. Л. Ершова, С. С. Марченкова, В. В. Вьюгина, С. А. Бадаева. Вопрос о возможном числе однозначных и позитивных нумераций различных семейств ОРФ и семейств РП множеств исследовался Ю. Л. Ершовым, А. Б. Хуторецким, С. С. Марченко-вьщ, С. А. Бадаевым, С. С. Гончаровым, и другими авторами.

Минимальные нелозитивные нумерации, в отличие от однозначных и позитивных, вплоть до недавнего времени были изучены сравнительно слабо. Были известны только три работы [12, 15, 18], в которых рассматривались вопросы о числе минимальных нелозитавных нумераций некоторых семейств РП множеств. Одной из причин сложившейся ситуации было отсутствие внутреннего описания минимальных нумераций и, вследствие этого, единственный подход к ним, как к нумерациям, порождающим минимальные элементы в полурешетках Роджерса.

В теории вычислимых нумераций хорошо известны две проблемы, поставленные Ю. Л. Ершовым во второй половине шестидесятых годов. Это проблема характеризации семейств с одноэлементной полурешеткой Роджерса и проблема описания спектра минимальных вычислимых нумераций. Первая проблема решена недавно для случая семейств общерекурсивных функций (ОРФ) С. С. Гончаровым [5] и М. Куммером [24]. Очень важные шаги по решению второй проблемы сделаны С.С.Гончаровым [2] доказавшим, что с точностью до зкви-

валентности число однозначных вычислимых нумераций может принимать любое из значений 0,1,2Аналогичный результат для позитивных вычислимых нумераций анонсирован им в [5].

Дальнейшее продвижение по обеим этим проблемам обусловлено, на наш взгляд, разработкой новых методов построения минимальных непозитявных нумераций.

Целью работы является нахождение внутренних критериев минимальности нумераций и разработка конструкций минимальных вычислимых нумераций доя

» классификации минимальных вычислимых нумераций,

• исследования семейств РП множеств как с одноэлементной, так в бесконечной лолурешеткой Роджерса,

в исследования спектра минимальных вычислимых нумераций некоторых классических семейств,

• решения других проблем, связанных с минимальными нумерациями.

Общая методиха исследования, В диссертации используются методы теории рекурсивных функций я методы теории нумераций.

Научная новизна. В диссертации предложен новый подход к исследованию минимальных нумераций, основанный на их внутренней хараетеризации, введены новые классы минимальных нумераций и разработаны эффективные методы их построения, позволяющие решить ряд известных проблем.

Практическая и теоретическая ценность. Работа носит теоретический характер. Ее результаты и методы могут применяться в исследованиях но теории нумераций, теории рекурсивных функций, теории конструктивных моделей, в теоретическом программировании. Результаты диссертации могут быть иснользованы при чтении специальных курсов и при подготовке монографий.

Апробация результатов диссертации. Результаты диссертационной работы докладывались автором на общегородском семинаре по алгоритмическим проблемам при Алматянсхом госуниверситете, на семинарах "Алгебра и логика" и "Теория нумераций" Новосибирского госуниверситета, в секционных докладах IX (Ленинград, 1988), X

(Алма-Ата, 19S0) Всесоюзных конференций по математической логике и III Международной конференции ио алгебре, посвященной памяти М. И. Каргояолова (Красноярск, 1993), в пленарном докладе на Международной конференции по математической логике, посвященной 85-летию со дня рождения А. К. Мальцева (Новосибирск, 1994).

Публикации. Результаты диссертации опубликованы в работах [27]-[45].

Объем и структура работы. Диссертация изложена на 195 страницах и состоит из введения и 4 глав, рабитых на 11 параграфов. Номера параграфов содержат номер главы, а номера утверждений и определений — номер параграфа. Библиография содержит 99 наименований, включая работы автора по теме диссертации.

Автор выражает глубокую благодарность своему Учителю, Юрию Леонидовичу Ершову, влияние которого предопределило направление его исследований на долгие годы.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении кратко охарактеризовано современное состояние проблематики минимальных вычислимых нумераций, очерчен круг вопросов, которым посвязцена диссертационная работа, дана качественная оценка основных результатов, описана структура диссертационной работы.

Глава I состоит из трех параграфов и носит предварительный хаг рактер. В ней приводятся все необходимые понятия и используемые обозначения, дается обзор развития теории вычислимых нумераций, в котором основное внимание уделено проблемам, связанным с минимальными нумерациями, и формулируются основные результаты диссертации. Собственно результаты диссертационной работы излагаются в главах II - IV.

В дальнейшем мы придерживаемся понятий и обозначений из монографий [8] и [15]. Говоря о числе каких-либо нумераций, мы подразумеваем это число с точностью до эквивалентности нумераций. Через N обозначается множество натуральных чисел, через ва — нумерационная эквивалентность {< г,у >: ах — o¿y} нумерации а, а через [Ai]* — замыкание множества М С N относительно эквивалентности е на N.

в

Глава 1Г, состоящая из трех параграфов, посвящена описанию внутренних критериев минимальности нумераций, классификации минимальных нумераций и применению полученных критериев в исследовании иолурешеток Роджерса, содержащих идеалы без минимальных элементов.

В параграфе 2.1 получены несколько критериев минимальности нумераций, среди которых следующий оказался наиболее удобным в применении:

ТЕОРЕМА 2.1.2. Нумерация а произвольного множества является минимальной тогда и только тогда, когда для каждого РП множества W С N такого, что — N, существует позитивная эквивалентность г} С. 8а , для которой [И*7], =

Как легко заметать, в формулировке теоремы 2.1.2 нет обращения к другим нумерациям множества. В ней используются только нумерационная эквивалентность 0а и общие понятия теории рекурсивных функций. Таким образом, полученная характернзация минимальных нумераций является внутренней.

В параграфе 2.2 предложен естественный, на наш взгляд, подход к классификации минимальных нумераций. Пусть а — минимальная нумерация. Из критерия минимальности (теорема 2.1.2) следует, что каждому РП множеству Wt удовлетворяющему некоторым условиям, можно поставить в соответствие позитивную эквивалентность г/, являющуюся разбиением <?„, и относительно которой замыкание W есть N. Чем эффективнее процесс построения Tj по W и ва , тем нумерация а "проще" с алгоритмической точки зрения.

В соответствии с этим подходом естественно возникают два новых класса минимальных нумераций.

ОПРЕДЕЛЕНИЕ 2.2.1. Нумерация а называется эффективно минимальной, если существует ЧРФ h(n) такая, что для любого п € N, если [Wn]i„ = N, то h(n) определено, ch(n) С ва и — N.

ОПРЕДЕЛЕНИЕ 2.2.3. Нумерация а называется строго эффективно минимальной, или для краткости строго минимальной, если существует позитивная эквивалентность г}С$а такая, что для любого » € N, если [Wn}So = N, то [Wn], = N.

Обозначим через D, Р, SM, ЕМ, М соответственно классы разрешимых, позитивных, строго минимальных, эффективно минимальных и

минимальных нумераций. Очевидно, что О С Р С 8М С ЕМ С М. Известно, что В С Р [7,12,19] и Р С М [12, 20].

Основные результаты параграфа 2.2 позволяют представить классификацию минимальных вычислимых нумераций в виде цепочки включений В С Р С 8М С ЕМ С М. Примеры, показывающие строгость включений Р С БМ (теорема 2.2.10) и ЕМ С М (теорема 2.2.9), получены в классе вычислимых нумераций дискретных семейств.

ЗАМЕЧАНИЕ 2.2.11. Семейства, построенные в теоремах 2.2.9 и 2.2.10, являются позитивно вычислимыми, а их полурешегки Роджерса содержат бесконечно много минимальных элементов.

В [8, 11] показано, что в полурешетках Роджерса семейств ОРФ и конечных семейств РП множеств всякий идеал содержит минимальные элементы. Известно, что полурешетка И{Р) имеет как идеалы, содержащие минимальные элементы, так и идеалы без минимальных элементов [7, 20]. И, наконец, в [1] доказано существование вычислимых семейств РП множеств, полурешетки Роджерса которых вовсе не имеют минимальных элементов.

При построении идеалов полурешеток Роджерса оказалась полезной внутренняя характеризация нумераций, порождающих главные идеалы без минимальных элементов, основанная на критерии минимальности нумераций. Она приведена в теореме 2.3.4 и используется в теореме 2.3.5 при решении известной проблемы С.С.Гончаровым из [9]. В теореме 2.3.6 приведены структурные условия существования в полурешетках Роджерса счетного числа попарно не пересекающихся главных идеалов без минимальных элементов. Сформулируем теперь основные результаты параграфа 2.3.

ТЕОРЕМА 2.3.2. Существует вычислимое дискретное семейство РП множеств, полурешетка Роджерса которого не имеет минимальных элементов.

Проблема построения вычислиых семейств, не имеющих минимальных вычислимых нумераций, была поставлена Ю. Л. Ершовым в конце 60-х годов в связи с поиском аналога известной в теории алгоритмов теоремы М. Блюм об ускорении. Впервые существование такого семейства было доказано В. В. Вьюпшым [1] с помощью довольно сложной приоритетной конструкции. Теорема 2.3.2 доказывается простым диагональным построением. Второе отличие теоремы 2.3.2

от теоремы В. В. Вьюгипа состоит в структурном различии построенных семейств. В пашем примере семейство не имеет предельных точек, в то время как в примере В. В. Вьюгина содержится бесконечно много предельных точек, и это обстоятельство существенно для его конструкции.

С. С. Гончаровым [9] поставлен вопрос, который можно переформулировать так: всякий ли идеал в полурешетке Роджерса однозначно вычислимого семейства РП множеств содержит минимальные элементы? Семейство "Р всех РП множеств дает отрицательный ответ на этот вопрос.

Следующие две теоремы усиливают отрицательное решение проблемы С. С. Гончарова в двух направлениях: во-первых, строятся семейства с наиболее простой внутренней структурой, а, во-вторых, исследуются семейства, в полурешетках Роджерса которых бесконечно много попарно не пересекающихся идеалов без минимальных элементов.

ТЕОРЕМА 2.3,5. Существует однозначно вычислимое дискретное семейство, полурешетт Роджерса которого содержит главный идеал без минимальных элементов.

А. В. Хуторецким [20] найдены структурные условия для семейств, полурешетки Роджерса которых содержат счетное число главных идеалов без минимальных элементов. Оказывается, что условия Хуто-рецкого можно ослабить, а соответствующие идеалы строить попарно не пересекающимися.

ТЕОРЕМА 2.3.6. Пусть семейство В РП множеств есть объединение подсемейств Во « Вг таких, что

1) Во состоит из бесконечных множеств « является однозначно вычислимым;

2) Sj — сильно вычислимое семейство конечных подмножеств множеств из So, « каждое В € 8а есть объединение возрастающей последовательности множеств из

Тогда семейство В однозначно вычислимо и имеет вычислимую нумерацию, к которой не сводится ни одна минимальная нумерация семейства 8.

СЛЕДСТВИЕ 2.3.10. В полурешетке ЩР) содержится счетное число попарно tie пересекающихся идеалов без минимальных элемен-

тов.

Один мз принципиально важных результатов теории нумераций — теорема А. Б. Хугорецкого [21], согласно которой всякая лолурешетка И{Л) либо одноэлементна, либо счета, — устанавливает взаимозависимость между исследованиями семейств как с одноэлементной, так н бесконечной полурешеткой Роджерса. С другой стороны, все вычислимые нумерации семейств с одноэлементной полурешеткой Роджерса являются минимальными. Таким образом, исследование мощности полурешеток Роджерса различных семейств тесно связано с исследованиями минимальных нумераций.

Внимание многих авторов уделялось большей частью изучению семейств ОРФ с одноэлементной полурешеткой Роджерса. В главе III выявляются принципиально новые моменты в описании семейств РП множеств как с одноэлементной, так и бесконечной полурешеткой Роджерса (теоремы 3.1.2, 3.1.7, следствие 3.3.3).

Семейства с одноэлементной полурешеткоЙ Роджерса исследовались во многих работах. А. И. Мальцевым [11] замечено, что все вычислимые нумерации эффективно дискретных семейств являются позитивными и, следовательно, полурешетки Роджерса таких семейств одноэлементны. Ю. Л. Ершов [6]доказал, что семейства ОРФ с одноэлементной полурешеткой Роджерса могут быть только дискретными. Примеры дискретных, но не эффективно дискретных семейств ОРФ Л с одноэлементной полурешеткой ЩЛ) построены С. А. Бадаевым [27] и В. Л. Селивановым [16]. Известны также два примера семейств РП множеств Л с одноэлементной полурешеткой И(А) — пример В. В. Выогина [1] слабо эффективно дискретного семейства и пример В. Л. Селиванова [17] недискретного семейства. Необходимые и достаточные условия одноэлементности полурешеток Роджерса семейств ОРФ получены С. С. Гончаровым [5] и М. Куммером [24]. Фактически, оба последних критерия дают алгоритмическую харак-теризацию позитивных вычислимых нумераций дискретных семейств ОРФ.

Общим во всех приведения: выше работах является то, что рассматриваемые в них одноэлементные полурешетки Роджерса порождаются либо однозначными, либо позитивными нумерациями. В параграфе 3.1 исследуется вопрос о том, какими нумерациями могут иоро-

ждаться одноэлементные голурешетки Роджерса. Основные результаты этого параграфа содержатся в следующих двух теоремах.

ТЕОРЕМА 3.1.2. Существует дискретное семейство РП множеств с одноэлементной полурешеткоЫ Роджерса, порожденной минимальными, но не эффективно минимальными нумерациями.

ТЕОРЕМА 3.1.7, Существует дискретное семейство РП множеств с одноэлементной полурешеткой Роджерса, порожденной строго минимальными непозитивными нумерациями.

Эти теоремы позволяют также ответить на вопрос о том, какими могут быть вычислимые нумерации, порождающие наименьшие элементы в полурешетках Роджерса. Все известные ранее наименьшие нумерации были либо разрешимыми, либо позитивными. Как оказалось, существуют семейства РП множеств, как дискретные, так и недискретные, имеющие наименьшие вычислимые нумерации из классов М \ ЕМ, SM\P (следствия 3.1.4, 3.1.9).

Другая группа следствий показывает, что многие семейства РП множеств, и среди них семейство V, имеют счетное число минимальных вычислимых пумераций в каждом из классов М \ ЕМ, SM\P (следствия 3.1.5, 3.1.10, 3.1.11).

В. Л. Селивановым [17] построено недискретное семейство РП множеств с одноэлементной полурешеткой Роджерса, не содержащее вложенных множеств. В связи с этим им был поставлен вопрос о том, всегда ли полурешетхи Роджерса семейств, содержащих пары вложенных множеств, являются бесконечными. До конца семидесятых годов положительное решение этого вопроса казалось наиболее вероятным. В параграфе 3.2 доказывается следующая теорема, отвечающая на вопрос В. JI. Селиванова.

ТЕОРЕМА 3.2.1. Существует нетривиальное семейство PIT множеств, содержащее наименьшее по включению множество, полурешетка Роджерса которого одноэлементна.

Отметим, что этот результат был одновременно и независимо получен С. С. Гончаровым и опубликован в совместных с автором работах [41, 45].

Отрицательное решение проблемы В. Л. Селиванова сделало еще более актуальным нахождение структурных и алгоритмических условий бесконечности полурешеток К(А) для семейств А, содержащих

хотя бы одну пару вложенных множеств. Несколько таких признаков приводятся в параграфе 3.3.

Напомним некоторые естественные классы семейств, содержащих пары вложенных множеств, с бесконечными полурешетками Роджерса. Это конечные иедискретные семейства и семейство всех РП множеств [8], семейства, не замкнутые относительно объединения вычислимых неубывающих последовательностей [25], семейства, имеющие наибольшие по включению множества [28]. Некоторые достаточные признаки бесконечности полурешеток Роджерса нумераций можно получить переформулировкой результатов С. С. Марченкова [12, 13}.

ОПРЕДЕЛЕНИЕ 3.3.1. Пусть А, В — произвольные подмножества множества N. Тогда А наывается эффективно отделимым от В, если существует РП множество для которого А С Уг7 к В ПЪУ —

ТЕОРЕМА 3,3.2. Пусть семейство РП множеств Л содержит пару вложенных множеств А С, В и имеет вычислимую нумерацию а, для которой (Л) эффективно отделимо от а~1(В). Тогда по-лурешетт Роджерса К(А) бесконечно..

СЛЕДСТВИЕ 3.3.3. Если семейство РП множеств содержит пару вложенных множеств и допускает позитивную вычислимую нумерацию, то его полурешетка Роджерса бесконечна.

ТЕОРЕМА 3.3.4. Пусть семейство РП множеств А содержит пару множеств А С В. Вели N\B эффективна отделимо от А, то полурешетка Роджерса 7£(Л) бесконечна.

Заметим, что условие эффективной отделимости множества N \ В от множества А посредством РП множества Д равносильно цепочке включений А С N \ В. С В.

СЛЕДСТВИЕ 3.3.6. Пусть семейство А содержит пару вложенных множеств А С В, и пусть существует РП множество С такое, что А ^ С С. В и{}А\С — РП множество. Тогда полурешетка ЩЛ) бесконечна.

Отметим, что идейным источником теоремы 3.2.1 послужили результаты и конструкции параграфа 3.3, позволившие выявить причины, вследствие которых полурешетка Роджерса семейства, содержащего вложенные множества, оказывается бесконечной.

Целью главы IV является описание спектра минимальных вычислимых нумераций семейств РП множеств, нумерации которых предельно

эквивалентны между собой.

ОПРЕДЕЛЕНИЕ 4.1.1 (С. С. Гончаров [3]). Нумерация а множества А предельно сводится к нумерации множества А, если а = для некоторой (^-рекурсивной функции /. Если нумерации а и /3 предельно сводятся друг к другу, то они называются предельно эквивалентными.

В параграфе 4.1 по аналогии с полурешеткой Роджерса вводится верхняя полурешетка 72'(Л) классов предельно эквивалентных вычислимых нумераций семейства РП множеств А, позволяющая взглянуть на некоторые известные результаты с новой точки зрения, а также сформулировать направление дальнейших исследований по проблеме описания спектра минимальных вычислимых нумераций.

Основной результат параграфа 4.1 (теорема 4.1.2) носит технический характер и существенно используется в параграфе 4.2. Эта теорема. представлет, по нашему мнению, также и самостоятельный интерес.

ТЕОРЕМА 4.1.2. Для любого семейства РПМА и любых его предельно эквивалентных; попарно несравнимых нумераций70)7ь'' * >7п-х» где, п > 1, существует нумерация ¡3 семейства А, предельно сводящаяся к 7о и к которой не сводится ни одна из нумераций 7;, г < п.

СЛЕДСТВИЕ 4.1.3 (С.С.Марченков [14]). Если семейство ОРФ А имеет две однозначные вычислимые нумерации, то А имеет счетное число такиг нумераций.

СЛЕДСТВИЕ 4.1.4 (С.А.Вадаев [28]). Если слабо эффективно дискретное семейство РП множеств А имеет две позитивные вычислимые нумерации то А имеет счетте число таких нумераций.

В параграфе 4.2 исследуется вопрос о числе минимальных нумераций, содержащихся в элементах палурешеткн И'(А), порожденных позитивными нумерациями.

Такой подход к проблеме описания спектра минимальных вычислимых нумераций возник в связи с теоремой С. С. Гончарова [4] о том, что семейства, обладающие однозначной, но не наименьшей вычислимой нумерацией, имеют счетное число позитивных вычислимых нумераций.

Основной результат параграфа 4.2 — георема 4.2,1 — яаляется локальным аналогом теоремы Гончарова в случае позитивных нумера-

дий. Возможность переноса результата Гончарова на позитивные нумерации в общей ситуации не известна.

ТЕОРЕМА 4.2.1. Среди нумераций, предельно эквивалентных произвольной позитивной вычислимой нумерации, либо есть наименьшая, либо существует счетное число минимальных вычислимых нумераций.

СЛЕДСТВИЕ 4.2.2. Вычислимые семейства каждого из следующих классов — ОРФ, конечных множеств, слабо эффективно дискретных семейств — имеют либо наименьшую нумерацию, либо бесконечно много минимальных вычислимых нумераций.

Отметим, что для класса семейств ОРФ утверждение следствия 4.2.2 эквивалентно теореме С. С. Марченкова [14], а для классов семейств конечных множеств и слабо эффективно дискретных семейств проблема числа позитивных нумераций решена соответственно в [28] и[3].

В примере С. С. Гончарова [23] семейства с единственной позитивной, но не наименьшей вычислимой нумерацией все множества семейства являются конечными. Следовательно, это семейство имеет счетное число минимальных вычислимых нумераций. В связи с этим представляется интересным исследование следующего вопроса: существуют ли семейства РИ множеств, допускающие единственную минимальную вычислимую нумерацию, которая является непозитивной и ненаименьшей.

СЛЕДСТВИЕ 4.2.3. Пусть А - произвольное вычислимое семейство одного из следующих трех классов: ОРФ, конечных, множеств, слабо эффективно дискретных семейств. Тогда полурешетка Роджерса "Л(Л) имеет либо наименьший элемент, либо счетное число минимальных элементов.

Литература

[1] Вьюгин В.В. О некоторых примерах верхних полурешеток вычислимых нумераций. Алгебра и логика. 1973. Т.12. N.5. С. 512-529.

[2] Гончаров С.С. Однозначные вычислимые нумерации. Алгебра и логика. 1980, Т. 19. N.5. С.507-551.

[3] Гончаров С.С. Предельно эквивалентные конструктивизации. Труды Ин-та математики СО АН СССР. 1982 Т.2. С. 4-12.

[4] Гончаров С.С. Позитивные нумерации семейств с однозначными нумерациями. Алгебра и логика. 1983. Т.22. N.5 С.481-488.

¡5] Гончаров С.С. Позитивные вычислимые нумерации. Доклады Академии наук (России). 1993. Т.332. N. 2. С. 142-143.

[б] Ершов Ю.Л. Нумерации семейств общерекурсивных функций. Сиб. матем. ж. 1967. Т.8. N.5. С.1015-1025.

[7} Ершов Ю.Л. О вычислимых нумерациях. Алгебра и логика. 1988. Т.7. N.5. С.71-99.

[8] Ершов Ю.Л. Теория нумераций. — М.: Наука, 1977.

[9] Логическая тетрадь. — Новосибирск: Ин-т математики СО АН СССР, 1986.

[10] Мальцев А.И. Конструктивные алгебры, 1. Успехи мат. наук. 1961. Т.16. N.3. С.3-60.

[11] Мальцев А.И. Позитивные и негативные нумерации Докл. АН СССР. 1965. Т.160. N.2. С.278-280.

[12] Марченков С.С. О минимальных нумерациях систем рекурсивно перечислимых множеств. Докл. АН СССР. 1971. Т. 198. N.3. С.530-532.

[13] Марченков С.С. О полуструктурах вычислимых нумераций. Докл. АН СССР. 1971. Т. 198. N.4. С.766-768.

[14] Марченков С.С. О вычислимых нумерациях семейств общерекурсивных функций. Алгебра и логика. 1972. Т.Н. N.5. С.588-607.

[15] Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.

[16] Селиванов В.Л. О нумерациях семейств общерекурсивных функций. Алгебра и логика. 1976. Т.15. N.2. С. 205-226.

[17] Селиванов В.Л. Две теоремы о вычислимых нумерациях. Алгебра и логика. 1976. Т.15. N.4. С.470-484.

[18] Селиванов В.Л. О нумерациях канонически вычислимых семейств конечных множеств. Снб. матем. ж. 1977. Т.18. N.6. СЛ373-1380.

[19] Хуторецкий А.Б. О сводимости вычислимых нумераций. Алгебра и логика. 1969. Т.8. N.2. С.251-264.

[20] Хуторедкий А.Б. Две теоремы существования для вычислимых нумераций. Алгебра и логика. 1969. Т.8. N.4. С.483-492.

[21] Хуторедкий А.Б. О мощности верхней полурешетки вычислимых нумераций. Алгебра и логика. 1971. Т.10. N.5. С.561-569.

[22] Friedberg R.M. Three theorems on recursive enumeration. J. Symbolic Logic. 1958. V.23. N.3. Р.30Э--316.

[23] Goncharov S.S. A unique positive enumeration. Siberian Adv. Math. 1994. V.4. N.l. P.52-64.

[24] Kummer M. A learning-theoretic characterization of discrete families of recursive functions. Information Processing Letters, 1995, V.54, P.205-211.

[25] Lachlaa A.H. On the indexing of classes of recursively enumerable sets. J. Symbolic Logic. 1966. V.31. N.l. P.10-22.

[26] Rogers H. Godel numberings of partial recursive functions. J. Symbolic Logic. 1958. V.23. N.3. P. 49-57.

Работы автора по теме диссертации

[27] Бадаев С.А. О вычислимых нумерациях семейств общерекурсш-ных функций. Алгебра и логика. 1977. Т.16. N.2. С.129-148.

[28] Бадаев С.А. О позитивных нумерациях. Сиб. матем. ж. 1977. Т.18. N.3. С.483-496.

[29] Бадаев С.А. О минхлмалъных нумерациях. В кн.: Девятая всесо-юзн. конф. по матем. логике. Тезисы докладов. —Л.; Наука, 1988. С.10.

[30] Бадаев С.А. О минимальных нумерациях дискретных семейств. В кн.: Международен конф. по алгебре, посвященная памяти А. И. Мальцева. Тезисы докладов по теории моделей и алгебраических систем. — Новосибирск; Ин-т матем. СО АН СССР, 1989. С.7.

ie

[31] Бадаев С.А. О нижних конусах без минимальных элементов в полурешетках вычислимых нумераций. В сб.: Теория моделей. — Алма-Ата; ИздКазГУ, 1990. С.3-6.

[32] Бадаев С.А. Предельная сводимость к позитивные нумерации. В кн.: Советско-французский коллоквиум по теории моделей. Тезисы докладов. — Караганда: КарГУ, Ин-т математики и механики АН Каз ССР, 1990. С.З.

[33] Бадаев С.А. Об эффективно минимальных нумерациях. В кн.: Десятая воесоюзн. конф. по матем. логике. Тезисы докладов. — Алма-Ата: Ин-т математики и механики АН Каз ССР, 1990. С.10.

[34] Бадаев С.А. К одной проблеме С,С. Гончарова. Сиб. матем. ж.

1991. Т.32. N.3. С.212-214.

[35] Бадаев С.А. О мощности полурешеток нумераций. В кн.: Одиннадцатая конф. по мат. логике. Тезисы докладов. — Казань: КГУ,

1992. С.10.

[36] Бадаев С.А. Минимальные нумерации. Труды Ин-та математики СО РАН. Т.25. С.3-34.

[37] Бадаев С.А. О мощности полурешеток нумераций педискретпых семейств. Сиб. матем. ж. 1993. Т.34. N.5. С. 3-10.

[38] Бадаев С.А. Минимальные нумерации позитивно нумерованных семейств. В кн.: Третья международа, конф. по алгебре памяти М. й. Каргополова, Тезисы докладов. — Красноярск: "Инопроф",

1993. С.29,

[39] Бадаев С.А. Минимальные нумерации позитивно вычислимых семейств. Алгебра и логика 1994. Т.ЗЗ. N. 3, С.233-254.

[40] Бадаев С.А. Условия типа отделимости бесконечности полурешеток Роджерса. В кн.: Международная конф. по матем. логике, посвященная 85-летик> со дня рождения А. И. Мальцева. Тезисы сообщений. — Новосибирск: изд-во МИОО НГУ, 1994. С.16-1Т.

[41] Гончаров С.С., Бадаев С.А. Семейства с одноэлементной полурешеткой Роджерса. Препринт N. 15, 1998. НИИ МИОО Новосибирского госуниверснтета. 21 с.

[42] Badaev S.A. On minimal enumerations. Sibirian Adv. Math. 1992. V.2. N.l. P.i-30.

[43] Badaev S.A. Some problems on computable enumerations. Bulletin of Symbolic Logic. 1995. V.l. N.2. P.222.

[44] Badaev S.A., Goncharov S.S. On computable minimal enumerations. Algebra. Proceedings of the Third International Conference on Algebra, Dedicated to the Memory of M. I. K&rgopolov. Krasnoyarsk, August 23-28, 1993. — Walter de Gnxyter, Berlin — New York, 1995. P.21-32.

[45] Goncharov S.S., Badaev S.A. Classes with pairmsc equivalent enumerations. Lecture Notes in Computer Science. 1994. V.813. P. 140-141.

Пописано к печати 06.11.96

Формат бумаги 60 х 84 1/16 Объем 1 пл.

Тираж 100 экз. Заказ 134

Компьютерный центр ЙТПМ HAH PK

480021, Алматы, ул. Пушкина, 125, ИТПМ HAH PK