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

1- АКАДЕМИЯ НАУК СССР

СИБИРСКОЕ ОВД-ПЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

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

на правах рукописи ДОБРИЦА Вячеслав Лорфирьевич

ВЬЭДСИЧ'№ ст/ССН КОНСТРУКТИВНЫХ МОДЕЛЕЙ

01.01.06 - математическая логика, алгебра и теория чисел

Автореферат

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

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

Диссертация выполнена в Казахском ордена Трудового Красного Знамени государственном педагогическом университете им.Абая.

Научный консультант - доктор физико-математических наук, . профессор С.С.Гончаров

Официальные оппоненты - доктор физико-математических наук,

профессор А.Н.Дегтев

- доктор физико-математических наук, профессор А.Л.Семенов

- доктор физико-математических наук, профессор В.Л.Селиванов

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

Защита состоится декабря 1991 года в ^ ^ часов

на заседании Специализированного совета Д 002.23.01 по защите диссертаций на соискание ученой степени доктора наук при Институте математики СО АН СССР по адресу: 630090, Новосибирск-90, Университетский проспект, 4.

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

Автореферат разослан " /У " ¡¿З^Я 1991 г.

Ученый секретарь

Специализированного совета Д 002.23.01 кандидат физико-математических наук

В.Г.Скосырский

Изучение алгоритмических свойств математических объектов всегда представляло большой интерес для ученых. Одним из наиболее продуктивных подходов к решению возникающих проблем в этих исследованиях явилось появление в середине 50-х годов на стыке теории алгоритмов и теории моделей новой теории - теории конструктивных моделей. Это направление проявилось в ряде работ Р.Л.Воота, А.МостовСкого, А.И. Мальцева, М.О.Рабина, А.Фрелиха, Д.Шефердсона и других авторов.

Как показали дальнейшие исследования наиболее удачные определения и понятия зарагкдагацейся теории были предложены А.И.Мальцевым (1961 г.). Суть подхода состоит в выборе такой нумерации элементов основного множества алгебраической системы (модели), что ее операции и предикаты, соотнесенные к нем ер см, становятся рекурсивными. Другими словами, на номерах элементов мы можем эффективно выполнять операции и распознавать истинность предикатов, в тем числе и предиката равенства.

В нашей стране теория конструктивных моделей сформировалась на основе работ академика А.И.Мальцева и получила бурное развитие под его руководством в конце 60-х, 70-е годи, в основная, в Сибирской сколе по математической логике, ныне возглавляемой член-корреспондентсм АН СССР О.Л.Еряо-вым. Подтверждением зрелого становления теории конструктивных моделей явилось издание монографии Ю.Л.Ершова (1980).

Больиая часть исследований велась в русле двух направлений:

-А-

1. Проблема существования конструктивизаций и конструк гивньк моделей;

2. Проблема числа неавтоэквивалентных кснструктивиэаци

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

тквы к изучению классов конструктивных моделей.

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

Идеи теории нумераций оказали сущесть*нное влияние на проблематику исследований вычислимых классов конструктивных моделей. Однако их изучение, требует собственных методов и подходов.. Для этих классов нумераций (в дальнейшем называемых индексациями) наряду с тоадиционньшг проблемами нумерованных объектов возникает и собственные, связанные со спецификой этих конструкций, объектов нумерации - конструктивных моделей.

Понятие вычислимого класса конструктивных моделей впер вые встречается при рассмотрении классов конструктивных рас тирений в работе Ю.Л.Ершова (1968 г.), а пример построения сильно вычислимого класса "ильно конструктивных моделей да-

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

При изучении второй проблематики возникает понятие тоустойчивости, которое было определено А.И.Мальцевым 962 г.). Число неавтоэквивадентных конструктивных нумера-:й у модели в дальнейшем было принято в качестве алгорит-теской размерности модели (Гончаров С.С., 1982 г.). В ■ом смысле автоустойчивкми является конструктивизируемые дели с алгоритмической размерностью I. ¡Цл7А Ш-1

Изучение яопросов автоустойчивости привело к кеобхо-мости изучения классов конструктивных моделей, возможнос-[ гас эффективной индексации, т.е. вычислимости. Однако, для гракого класса конструктивных моделей класс конструктивней не является вычислимым.

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

В 80-е года теория конструктивных моделей через свои :тоды и идеи получила тесную взаимосвязь с задачами созда-1Я логического программирования, в которых существенную эль играют абстрактные типы данных. Как отметили А.Н.Кол-згорйв и В.А.Успенский, вычислимые нумерации являются ес-гственной семантикой для исследования алгоритмических язы-5В программирования. Возникновения нового поколения языков рограммирования с аксиоматическими типами данных такте ста-1Т задачу изучения вычислимых индексаций классов конструк-

тивных моделей, а не только семейств частично рекурсивных функций. Действительно, на баш данных можно смотреть как на сильно конструктивную модель. Это - конечное множество с определенными на нам отношениями, совокупность которых т< же конечна. По системе аксиом, определяющей структуру баш« данных, задается вычислимый класс конструктивных моделей: класс состояний банка данных в каждый момент дискретно мен; ющегося времени, что соответствует процессам в ЭВМ.

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

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

Определение I. Модель Ш = Св1..._гСА> называется конструктивизируемой, а нумерация конструтстивной (или.конструктявизацией) и пара(¿71,1?) конструктивной моделью, если рекурсивно множество всех атомных и отрицаний автономных предложений, истинных з системе Щ ^ , которая получается из системы обо-гшдением сигнатуры р™*..., Рете; С*,..., с4 }

модели Ж до сигнатуры= 4 й } и

означиванием константых символов, с о от ле ст вующими нумерации I? элементами модели, т.е.

Определение 2. Модель Щ называется сильно конструктивизируемой , а пара (¡71.?) - сильно конструктивной, ее-

ли разрешима элементарная теория ТЦ(Ши) модели \7 сигнатуры .

Как абстрактный модели рассматриваются с точностью до изоморфизма, тан конструктивные и сильно конструктивные модели рассматриваются с точностью до автоэквквалентности.

Определение 3. Конструктивные (сильно конструктивные) и одели и (71,1?) называются конструктивно изоморфны-

ми, а 1-ту?.1ерац11И и I? эквивалентными (автоэквива-

лентньми), если существуют такие изоморфизм 'р ■■ 771 ^^Ъ

и общерекурсивная функция /бж) , что коммуникативна диаг-

а/ ЛСзО ¡^1 £ „ „

рамма ^ , т.о. выполняется равенство-/«

7П ги

Цпя нумерации в этед случае применяется следующее обозначение р. « г?.

При рассмотрении совокупности конструктивных моделей зстественно их учитывать с точностью до автооквивалентности. 1с трудно заметить, что в определении конструктивности (си-, тьной конструктивности) Требование ргкурсивности множеств®

можно заменить на равносильное ему требование рекурсивно?» перечислимости множества 0(Ш р) [ТА (Ш I/) ) • ото дает возможность определить вычисли-юсть класса конструктивных или сильно конструктивных ал-'ебраических сг тем.

Определение 4. Класс X конструктивных сисгеи(Щ,&) вычисли,!, если существует общерекурсивная функция я) •акая, что для каждого П функция {(п., х.) перечисляет тгасество О ($1 г") » гдв конструктивная система ютоэквивалеятна некоторой системе из класса Л* и для .аждой системы из класса ЗС существует соответствующее

значение п£ & .И класс, 1* называется сильно вычислимым, если указанная функция х) перечисляет множество пет 0) с удовлетворением всех остальных указанных требований.

Конструктивную нумерацию 1?" , соответствующую номе ру а для функции 4 (п, х) > обозначим через £ г-.

Таким образом задается эффективная итерация <Г Л/--

конструктивных моделей из класса ?С , которую назовем вычислимой индексацией класса К конструктивных моделей*

В противна/: случае класс УС конструктивных систем называется невычиелимым.

Понятие эффективно бесконечного класса введено С.С.Гс чдровьм (1980 г.). Оно уточняет понятие невычислимости.,

Гпределекие 5. Класс Ж называется эффективно бесконечным , если по любому вычислимому подклассу ~ " эффективно указывается элемент из разности -X' \ /"'. Ясно, что эффективно бесконечный класс является не вычислимым. Однако, эти понятия не. совпадают. Впервые это устано лета докладчиком (1983 г.).

ТЕОРЕМА I. Существует невычислимый класс конструкта) ных моделей, который не является эффективно бесконечным. Построенный класс содержит конструктивкзацию одной

абелевой группы 2 2 (Рп) , правда, не все ее к оке тру; пи

тивизации. Усиление этого результата получено Ю.Г.Венцо-вым (1987 г.). -

Дня широкого класса конструктивных моделей класс вс! конструктивизаций не является вычислимым и часто будет да к;е эффективно бесконечен. Достаточные условия эффективной

гсконвчности классов конструктивных моделей установлены", например, в работах /"2, 6, II, 43, 49/.

Целенаправленное изучение вычислимых классов конструктивных моделей ведется уже более 15 лет. Все результаты можно условно разбить на 4 направления.

1. Выделение вычислимых и сильно вычислимых классов конструктивных моделей.

2. Изучение индексных множеств вычислимых индексаций.

3. Изучение различных сводимостей вычислимых индексаций.

4. Изучение свойств полурешеток вычислимых индексаций.

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

Пусть Т является вычислимой индексацией класса ^ конструктивных алгебраических систем и "К0 — X ? множество 2 у а (¿71 уп, Хц)еТ<<,} называется индек сдам множеством подкласса У\а в вычислимой индексации у класса X • Если . по дел ас с Х> состоит из одной модели (Щ, , то соответствующее индексное множество подкласса Ко называется индексным множеством конструктивной модели и обозначается следующим образш: Г--/^{ОЯ.^]).

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

ТЕОРЕМА 2. Для каждой вычислимой индексации X клас-са^С и произвольной конструктивной системном, &) 6 "К индексное множество/ ^ лежит в классе ¿Г0 арифметической иерархии множеств. Причем, для каждого множества л из клас са существует такие , У , р , что /4,

т.е. указанная оценка является точной.

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

ТЕОРЕМА 3. Для любой вычислимой индексации у конечного классаТ- {(&с,Я '¡.)/с-0,конструктивных сис' тем индексные множества Iлежат в классе . Существует такой класс К={(Ак+1, - О, /г| и его вычислимая индексация £ , что индексное множество Iлежит в А\ и не лежит в меныйпе. классах арифметической иерархии мнсжес'

Как следствие из доказательство этих двух утверждений получается следующий результат-.

ТЕОРЕМА, 4. Существуют такой вычислимый класс ^ конструктивных периодических абелевых групп и его вычислимая индексация . что все индексные множества/^ конструк-

тивных систем из класса 7С имеют сложность не ниже А 3 , причем, бесконечное число индексных множеств лежат в классе и не лежат в меньших классах арифметической иерархга

лнажеств.

R третьем параграфе за счет равномерного эффективного перехода от вычислимого семейства 5* рекурсивно перечис-гскмых (р.п.) множеств к вычислимому классуjkT^ конструктивных систем устанавливается точная оценка П° сложности индексных множеств моделей d вычислимых индексациях классов попарно конечно-различимых конструктивных моделей. Для вычислимых классов конечных моделей точной оценкой слозкнос-ги индексных множеств является класс ¿2^ в иерархии Ер-лова.

Модель fól называется локально влозеимой в модель Я

, ¿ - ft) > если каждая конечная подмодель модели 371 изоморфно вкладывается в модель 71 (Щ0 с.—- Yl) ■ 2ели одна из моделей Yft , 71 нэ вкладывается локально в цругуп, то эти модели называются коночноразличшьмм.

.По модели(Шу, i?) класса,^ конструктивных систем определим подклассы: L\j- - локальный подкласс, К - локальный кон ус .

Обозначим через L, подкласс класса JC , в который входят системы из JC локально влестимые во все системы класса JC Изучению индексных множеств этих естественных подклассов вычислимого класса конструктивных моделей посвящен четверти параграф этой главы.

ТЕОРЕМ 5. Пусть у - вычислимая индексация класса )? конструктивных моделей \i(1(1(]^)ü)g'J<! , тогда

е ni,jr(Kg) <5 П2\ l*(L)e П°

Для произвольного множества /\ <£ [7% существуют вычислимые классы ]Сд , , ЛА и такие их вычислимые индексации

Для индексного множества конструктивной модели естественен вопрос о снижении его сложности. Более точно этот вог рос формулируется следующим образом: возможно ли по вычислимой индексации X и конструктивной нумерации найти т доказать существование такой вычислимой индексации ОС этогс

же класса конструктивных моделей, что множество/^ имеет

т

меньшую арифметическую сложность, чем у ^ ?

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

ТЕОРЕМА 6. Существуют вычислимый класс УС , его выч] лимая индексация % и конструктивная модель (Ш^, так» что Т^¿57 " к ни в какой вычислимой индексации этого

I? 1

класса индексное множество этой модели, ¿7) не.монет быть рекурсивным.

Однако, достаточно просто устанавливается воачакность понижения сложности индексного множества с класса /7, р . Более сложно устанавливается следующий результат. ТЕОРЕМА 7. Если в вычислимом нетривиальном классе Ь конструктивных локально вычислимых друг в друга систем не которая система (¿71 ^_ подходящей вычислимой ивдексацт класса /, имеет индексное,множество,/^ из класса то существует вычислимая индексация ^ этого же класса Ц в которой индексное множество/'^ рекурсивно..

Наконец, отметим существование вычислимого класса и конструктивной системы (т I/) таких, что в любой вычислимой индексации (£ индексное мнсшествоТ"^ лежит в клас-

се£?з \п/'

Сводимость индексаций с>С ' на языке индексных множеств монно определить следующим образом:

а ^ /< =>3 / - о.р.ф. ) £2г

Аналогично определяется сводимость индексаций по локальным класса: /<4=^ - Уо £

о ) • Ясно. 470 из обычной сводимости ¿¿б/ следует сводимость по локальны« классам ^ Я ' '

По каждой из этих сводим остей естественным. образа.! определяются эквивалентности вычислимых индексаций, л ы. ^ / л / г» сг -

/ <!=:5> л ^ У3 Л ^ ^ СС ,

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

$ й ^ . Тогда по прямой сумме индексаций

и , если п. - четное;

гр-< » если нечетное >пределяется точная верхняя грань:

Соответствующие полурепетки обозначим через к

(У?) * Если же мы рассматриваем сильно вычислимые индексации класса^ сильно конструктивных моделей, то для обозначения полуреаетсж дополнительно введем л верхним индексом: , ¿Р $ (К).

Изучению сводимости по локальным классам спектра мощностей полурешеток (сильно) вычислимых индексаций классов сильно конструктивных моделей и посвящена третья глава диссертации.

Основном результатом первого параграфа является следующий факт.

ТЕОРЕМА 8. Если у класса конструктивных систем шего-

^ у

ся две вычислимые индексации Л. £ о , то «существует тжая

*

вычислимая индексация 'С этого же класса, что сС- £

у^ г, 4 У.

''гч

Из этой теоремы следует, что если у класса имеется две вычислимые индексации оС , у не эквивалентные относительно сводимости по локальным классам, то у этого класса имеется бесконечное число неэквивалентных относительно сводимости по локальным класса.: вычислимых индексаций, т.е. мощность полурепетки (&*) счетна. Так как мощность рассматриваемых полурешеток связаны неравенствам (УС) / £ ^ ^ » т0 ДО* класса с, указанным свойствам

полурешетка тоже счетной мощности. .Крале того полу-

чаем, что спектр значений мощности патурашет:;;;/¿¿^ £К')/ является двухэлементны.! множества,! ^ 1, /¿^ .

Для вычислимого класса локально влпжвмкх конструктив-шх систем любые две вычислимые индексации <5удут эквивалентны относительно сводимости по локальным ¡классам. Однако,

как устанавливается во втором параграфе, у .каждого нетривиального такого вычислимого класса всегда имеется бесконечное число несравнимых между собой вычислимых индексаций. Соответствующие этим индексациям классы эквивалентных элементов из полурешетки (¡К) образуют эффективную бесконечную последовательность несравнимых между собой элементов. Полурешетка (2С) при наличии такой последовательности называется полурешеткой эффективно счетной-ширины. Таким образом, для нетривиального класса локально влажимых конструктивных систем полурешетка вычислимых индексаций будет эффективно счетной' ширины.

В классе конструктивных моделей особую роль играют сильно конструктивные: модели, в которых, как указывал А.И.Мальцев, наиболее, полно реализуется понятие эффективное ти. С этой точки зрения представляет интерес рассмотрение полурешетогс вычислимых и сильно вычислимых: индексаций классов конструктивных: моделей. В третьем параграфе доказывается, что спектром' мощностей таких полурешеток является двухэлементное множество^, Это вытекает из более общего результата.

ТЕОРЕМА. 9. Пусть ^ является классом конструктивных систем с разреиимыми ^ - теориями. Если у класса^ есть две неэквивалентные вычислимые ицдексации, то у этого класса имеется счетное число неэквивалентных вычислимых индексаций.

Если в- определении сводимости индексаций требование

существования, общерекурсивной функции заменить на существо-ло

вание Л , — функции-, то получаем определение предельной

сводимости. Имедао, индексация Л предельно сводится к индексации , если существует ¿" - функция /(х-) такая

что для каждого я cf ю выполняется автоэхвиваленгность

/3 О ' \ rtn.s J<rin.) ,

В этом определении требование существования ¿'0 - фу]

кцки можно заменить на равносильное требование существова-

кия общеренурсивной функции <р(п, х) , которая при каждом

Л » у _ >

фиксированном значении п шее? предел tp( п., *

Г) -г- ОО

Индексация d предельно сводится к индексации J* , еелк существует ойцереиурскЕная функция <р(п,х') талая, что для каждого у.d и) существует предел £lm с^(гг, тс) м выпе

'/7 —»- С"

няется ¡эквивалентность ^ J* eirn ^ fa ху . Эту свод;;-

мость обозначим следувщигл образом: CL ~ J* , а йункцгсо

<?(п./х) назовем предельно сводящей.

Если существует общерекурсивкая функция -ffoc) , ¡сото-

рая при каждом значении JC £ <¿> ограничивает сверху число

с:.!Он значений в последовательности ¥(0,"flí^J,

то соответствующая сводимость называется предельно?? огргш-

ченной (функцией -/(arj ). Саму функцию j fx) буде-.л нажллп

ограничившей ш&корирующей; предельно сводяго"») 1-у.«гзго

Т'ГЯ, а:) , или просто мажорантой. Заьсеткг, что есл/.

Í - мажоранта предельно сводящей функции <р (a, zz)

и для всэххс ш выполняется неравенство г

то функция -л ' X i является мажорантой ж ¡ . Orna-:;:«;:

но предельную'сводимость г( к р с маторантои -fix) б уде;.:

обозначать следую©»? оопазал:^ ^ /» . Двя ог'юзне-

'z,ff;c)"

пения ограниченной предельной сводимости Осз .¡ихспрог-гшм мажоранты используй.! етаьол —

Ясно, что из обычной сводимости £ следует ограниченно предельная сводимость сС ^ ^ , причем с маиоран-той О (ос) а С.

Изучении предельных сводкмостей вычислимых индексаций классов конструктивных моделей посЕящена четвертая глава диссертации. В первом параграф изучаются свойства множества М-(мат.ораиг предельно сводящих функций, осуществляющих сводиг.юсть ¿з / . Две мажоранты , и3' множества Л^еС,^) связываются отношением ^(х), если и только если множество ^(я)} конечно. Это отнесение^ на множества является частичные порядке ал. Сформулируем основные свойства этого частично упорядоченного множество.

ТЕОРЕМА 10. I. Любое конечное подмножество имеет точные верхетю и кижия» гран:!.

2. Если |д М$ ) , то в этом множестве пет минимальных элементов.

3. Если О £М (Ы, ^ ) , то эта тождественная функ-

/

ция является наименьшим элементам.

О существовании вычислимых индексаций с высокой слогх-

ностьо предельно сводятцих функций говорит следующий реэуль-

? ¡-. „

ТЕОРЕМ II. Пусть - вычислимая индексами класса конструктивных ачгебрадческиъ систем, Д - 27„" - мно-•?.ество($2^, 2. такие, Д с.

сТ^УКр) ^огда для любой оЗцерекурсивной функции 4(ж) существуют вычислимые индексации , у класса ,

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

ТЕОРЕМА' 12. I. Если у класса,^ конструктивных моделей имеются вычислимые индексации ее , а такие, что с* ^ >

2. Если укласса К конструктивных моделей имеются вычислимые индексации , у3 такие, что Ы-^- уЗ ^

^ Д*к ы. . «/хю-

Отсюда получается достаточное условие счетности полу-

о

решетки вычислимых индексаций.

СЛЕДСТВИЕ 13. Если у класса УС конструктивных моделей имеются вычислимый индексации оС , ^ такие, что

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

2,Л » у п.

длины /г * { вычислимых индексаций и Ы. оС

, С-м , £ . £ V- к + / л, , I

этого класса, для которой сс ^ Л <Х

V г.*

при ¿--с./г и к п. - I . Отсода.в частности, следует, что

банерное отношение ля^^д*Ы.

не является отношением эквивалентности. В то же время отношения > *

* с <

cCf/л ffu ъ г

o£| л/f л .

являются отнесениями эквивалентности.

Наконец, в последнем, четвертом параграфе четвертой главы доказывается следующая теорема.

ТЕОРЕМА 14. Если у класса конструктивных моделей имеются вычислимые индексации , которые удовлетво-

ряют условию сС Ф жз J3 , то полурешатка вычислимых индексаций класса J< будет эффективно счетной пирины.

В частности, если у класса конструктивных моделей имеются не предельно эквивалентные индексации, то полурешетка вычислимых индексаций этого класса эффективно счетной ширины. Этот результат контрастирует со свойствами предельно эквивалентных нумераций. Само понятие предельно эквивалентных нумераций введено С.С.Гончаровым (1982). В этой же работе установлено, что если у модели имеется две предельно эквивалентные, но неэквивалентные констр^тивизации, то модель будет счетной алгоритмической размерности. Акалоквяж результаты были доказаны для однозначных и позитивных раций. С другой стороны, С.С.Гончаров (1980) долезал существование для каждого п. модели, у которой алгерзщидаекая размерность равна /г . Ясно, что эти конструетдачдеции будут не предельно эквивалентными. Для класса® «анэтруктквных моделей в случае наличия не предельно эдкивалентных индексаций имеется бесконечное число неэквивалентных вычислимых индексаций.

В полурешетке У? определим две подполурешетки

Iл а, / де)л^/}•

Аналогично определяются подполурешетки??^ V) полурешетки вычислимых нумераций семейства $ рекур-

сивно перечислимых множеств.

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

ТЕОРЕМА 15. Существует функционал ф определения рекурсивно перечислимого множества по конструктивной модели, который каждой вычислимой индексации сС класса конструктивных моделей ставит в соответствие вычислимую нумерацию сС' семейства

заданную равенствами^ - •> ^л)) • Причем,

1) если^- - вычислимый класс моделей конечных мощностей, то по функционалу <р определяется иэалорфизм полурешеток ^(к) # ($ ) ;

2) если - вычислимый класс конечно различимых конструктивные моделей, то при каждой вычислимой индексации & класса^ функционал ф ' определяет изоморфизм подполуре-шеток

3) для вычислимых индексаций сС, ^ класса таких, что & У3 , функционал задает изоморфиам полуреше-

Отсюда, в частности, следует, что полурешетка вычисли-

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

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

ЪгяъвеЬ'к^пХис^}.

Множество В назовем 0 - простым подмножеством А ' , если В й /\ , 3 € @ и Д®1 каждого хбш из£ $А\Е> следует конечность р. п. множества \Х/гх. • Если В является^С^ - простым подмножеством множества А » то оно простое подмножество множества А

1Е0РЕМА 16. Пусть У - вычислимая индексация класса УС конструктивных моделей,(7Пу, таковы, .что

/'£) у/-^-2 и в^имеется,2 ° - простое поданожество. Тогда полурешетка^^Ч*) эффективно счетной ширины.

Калдый перечислимый подкласс вычислимого' класса конструк тивных моделей является, очевидно, вычислим®? класс о/. . В третьем параграфе даются некоторые дтаяаяяучныэ условия вычислимости других подклассов внчишшшго- класса. Между числом вычислимых индексаций'- зкяйг® класса и его вычислимого подкласса устанавливается' определенная связь. .

ТЕОРЕМА 17. Пусть - перечислимый подкласс вычислимого класса в некоторой вычислимой индексации и у клас-

c&3s0 имеется две неэквивалентные вычислимые индексации

J*2 . Тогда и у класса^ имеются неэквивалентные вычислимые индексации ¿г Щ j .

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

ТЕОРЕМ 18. Если для некоторой модели(77?^,1^и вычислимой индексации У класса конструктивных моделей индексное множество ) (I^(^tf)) лежит в классе Лz арифметической иерархии множеств, то класс (/{(¿Пр,^ tr>P)J) , вычислим.

В четвертом параграфе последней пятой главы диссертации устанавливается, что спектрам bosmckchhx значений мощности полурешетки конечного класса ¿/С конструктивных систем

является двухэлементное множество •[ ■/, Жо] •

Основные результаты диссертации опубликованы в работах /"7-42 J, Они докладывались на 7 и 10 всесоюзных конференциях по математической логике, на семинарах "Алгебра и логика", "Теория нумераций" и "Конструктивные модели" в НГУ и ИМ СО АН СССР, ка семинарах по математической логике МГУ и ЛОМИ, на городском семинаре по математической логике в г.Алма-Ате и на семинаре "Алгоритмические вопросы алгебры и теории моделей" Казахского государствеwonо пелуниверситета.

Автор выражает искреннюю благодарность участник ем этих семинаров за многочисленные полезные обсуждения результатов и проблематики проводимых исследований; а также глубоко признателен С.С.Гончарову за постоянное внимание к работе и моральную подцеркку.

1. Венцов Ю.Г. Семейство рекурсивно перечислимцх множеств с коночными классами. неэквивалентных однозначных вычислимых нумераций. // Логические методы в программировании. - Новосибирск, 1937. - Вып.120: Вычислительные, системы. - С. 105 - 142.

2. Гончаров О.С. Автоустойчивость и вычислимые семейства конструктивизаций. // Алгебра к логика. - 1975. - т.14,

JS 6. - С.64? - 680.

3. Гончаров С.С. Проблема числа неавтоэквивалентных конструктивизаций. // ДАН СССР. - 1980. т.25, № 2. С. 271 - 274.

4. Гончаров С.С. Проблема числа неавтоэквивалентных конструктивизаций. // Алгебра и логика. -1930. т.19, Ä 6. С.621 - 639. ■

5. Гончаров С.С. Предельно эквивалентные конструктивизадаи./ В кн.: Математическая логика и теория алгоритмов. Груды института математики СО АН СССР, .т.2. - Новосибирск, 1982. - С.4 - 12'.

6. Гончаров С.С. Дзгоев В.Д. Автоустойчивость моделей. // Алгебра и логика. - 1930. - т.19, MI. - С.45 - 58.

7. Добрица В.П. Вычислимые клэесн конструктивных абелевых групп. / В кн.: Материалы ХШ ВсеесжзноЛ научной студенческой конференции, посвященной памяти В.И.Ленина, (математика). - Новосибирск. - 1975. - С.25 - 26.

3. Добрица В.П. О рекурсивно нумер:>вэнных классах конструктивных рясгирениЗ л авгоустоЗчивых алгебр. // Сиб. ыа-

тем.а. - 1975. - 't .16, Ai 6. - C.II48 - Ш>4.

9. Добрица B.II. О вычислимых и строго вычислимых классах конструктивных алгебр. _/ В кн.: Материалы республиканской конференции молодых учета. - Алма-Ата.-"Нарса" КазССР, - 1976. C.I87.

10. Добрица В.П. Одно необходимое условие вычислимости. / В

■ кн.: IV Всесоюзная конференция по математической логике. - Кишинев. - "Штиинца", 1976. С.44.

11. Добрица В.П. Теорема о нешчислишх классах. / В ich.: Математические науки. Вып.З. - Алма-Ата, 1976. - С.3-8.

12. Добрица В.П. Бичаслшосгь некоторых luiaccoB конструктивных алгебр. // Сиб.кютеы.ж. - 1977. т.18, & 3. -С.570 - 579.

13. Добрица В.П. Замечание о вычислимых классах алгебраических систем. / В ich.: XV Всесоюзная алгебраическая конференция. ч.2. - Красноярск, 1979. - С.53.

14. Добрица В.Г.. О вичислншх арифметических классах конструктивных алгебраических систем. / В кн.: Ш Всесоюзная алгебраическая конференция. Тезисы докладов. 4.2. - Ленинград, 1931. С.46,

15. Добрица В.П. Вичислимш класси'с локально вложимими системе ми. / В кн.: Математика. (Тезисы докладов седьмой Казахстанской ме¡¡¡вузовской научной конференции по математике и механике.) - Караганда, 1932. С.132 - 133.

16. Добрица В.П. 0 сложности индексного множества конструктивной нумерации. / В ich.: 6-я Всесоюзная конференция по математической логике. - Тбилиси, 1931. С.60.

17. Добрица В.П. О числе вычислимых индексаций класса

конструктивных моделей. / В сб.: Исследования по конструктивным моделям. - Алма-Ата, 1982, - С. 14 - 22.

18. Добрица З.П. Сложность индексного множества конструктивной модели. // Алгебра и логика. 1983. т.22, 4. С.372-331.

19. Добрица В.П. О конечных классах конструктивных систем. / В кн.: УШ Республиканская межвузовская конференция по математике и механике. Тезисы докладов. - 4.2.: Математика. - Алма-Ата, 1984. - С.175.

20. Добрица В.П. О вычислимых классах конструктивных систем со сложными индексными множествами. / В кн.: УП Всесоюзная конференция по математической логике. Тезисы докладов. - Новосибирск. 1934. - С.61.

31. Добркца В.П. О вычислимых классах конструктивах периодических; абелевых групп. / В кн.: XVII Всесоюзная алгебраическая конференция. Тезисы сообщений. ч.1. - Кишинев, 1935. - С. 169.

22. Добрица В.П. Сложность индексных множеств вычислимых классов с конечная числом конструктивных систем. // Сиб.мзтем.ж. - 1936. т.27, № 5. - С.68-74.

23. Добрица В.П. Число вычислимых. индексаций конечных классов конструктивных моделей. // Матем.заметки. -

1936. - т.40, № I. - С.93-97.

24. Добрица В.П. Мощность полурешотки вычислимых индексаций класса сильно конструктивных моделей. / В кн. УШ Всесоюзная конференция по математической логике, тезисы докладов. - Москва, 1986. - С. 60.

25. Добрица В.П. Структурою свойства вычислимых классов

конструктивных моделей. // Алгебра и логика- - 1987. -т.2б, й I. - С.36-62.

26. Добрица В.П. Локальные классы и вычислимые индексации. // Алгебра и логика. 1987. - т.26, № 2. C.I62-I90.

27. Добрица В.П. О вычислимых классах конструктивных, систем с условием совместной лекальной влояимости. / В ¡ш.: Материалы XIX Всесоюзной алгебраической конференции. Тезисы докладов. - ч.1. - Львов, 1987. - С.84.

28. Добркца В.П. О годурешетнах вычислимых иадекеащй! классов конструктивных моделей. // Алгебра и логика. 1937.-Т.26,. Л 5. - С.558-576.

23. Добрица В.П. Об ограниченной продельной сводимости вычислимых индексаций классов конструктившх моделей. // Логические катода в программировании. - Новосибирск, ISS'/. - вш.120: Вычислительные системы. С.143-158.

30. Добрица В.П. Классы с ограниченно эквивалентными индексациями. // Прикладные петит математической логики. -Новосибирск, 1987. - вып.122: Вычислительные системы. -С.69-72.

31. Добрица В.П. О полурешетках аффективно счетной ширины. / В кн.: Всесоюзная II Конференция по прикладной логике. Тезисы докладов. - Новосибирск, 1988. - С.74.

32. Добрица В.П. Об эффективно бесконечных классах./ В кн.: IX Всесоюзная конференция по математической логике. Тезиси докладов. - Ленинград, 1988. - С.53.

33. Добрица В.П. Полиномиально ограниченные сводимости вычислимых индексаций. // Языки спецификаций и логическое программирование. / Вычислительные системы. - выл.124. -

Новосибирск, 1988. - С.46-61.

34. Добрица В.П. О перечислимте. подклассах вычислимого класса конструктивных моделей. / В кн.: Исследования по алгебраической теории чисел и конструктивной алгебре. / Тем.сб.научных трудов ШО КазССР. - Алма-Ата, 1988. -

С.52-56.

35. Добрица В.П. Типы данных и вычислимые массы конструктивных моделей. // Теория алгоритмов и ее приложения. / Вычислительные системы. - вып.129. - Новосибирск, 1989. - C.I23-336.

36. Добрица В.П. Вычислимость некоторых подклассов вычислимого класса конструктивных моделей. // Сиб.ыатем. ж. - 1989. т.30, М 3. - С.45-51.

37. Добрица В.П. Ограниченные сводимости вычислимых индексаций гаассов конструктивных моделей. / В кн.: Совершенствование воспитательного и педагогического процесса. Педагогические взыскания. - ч.З. - Алма-Ата, 1939. - С.14.

38. Добрица В.П. О полурешетках вычислимых индексаций классов сильно конструктивных.моделей. / В im.: Математика и механика. Тезисы докладов IX Республиканской конференции по математике и механике. - чЛ. - Алма-Ата, 1989. - С. 152. .

39. Добрица В.П. Вычислимые классы конструктивных моделей' с не предельно эквивалентными индексациями!, // Матем.заметки. - 1989. - т.46, » 4. - C.S-J3U

40. Добрица В.П., (Dobritea V.P. C>n Diraensiom olT Sernilattioes of Countable Indexing.) / В ют-r Международная конференция по алгебре, посвященная памяти А.И.

Мальцева. Тезисы докладов по теории моделей и алгебраических систем. - Новосибирск, 1989. - С.40.

41. Добрица В.П. Критерий строгой вычислимости класса конструктивных моделей. / В кн.: Советско-французский коллоквиум по теории моделей. (Тезисы докладов), - Караганда, 1990. - С.16.

42. Добрица В.П. О семействе локальных конусов. / В ген.: X Всесоюзная конференция по математической логике. Тезисы докладов. - Алма-Ата, "Гилим", 1990. - С.60.

43. Дробатун Б.Н. О невычислимости одного класса сильных конструктивизаций. / В кн.: IV Казахстанская межвузовская конференция по математике и механике. - Алма-Ата,

' 197?. - С.130.

44. Ershov Y.L. Numbered Fields. J/ Logic, Method, and Phil. Science, III. - .Amsterdam, 1968. - pp. 31-34.

45. Ершов ЮЛ. Конструктивные модели. / В кн.: Избранные вопросы алгебры и логики. - Новосибирск, - "Наука" СО, 1973. - С.Ш-130.

46. Ершо,. U.J1. Проблема разрешимости и конструктивные кодели. - М.: Наука, 1980.

47. Мальцев A.M. Конструктивна алгебры, I. // Успехи

мат.наук. - 1961. т.16, М 3. - С.3-60.

48. Мальцев А.И. К теории вычислимых семейств объектов. J/ Алгебра и логика. - 1964. - т.З, № 4. - С.5-31.

49. Нуртазин А.Т. Сильные и слабые конструктивизаций и вычислимые семейства. // Алгебра и логика . - 1974. -т.13. # 3. - С.5П-Б23.

50. Успенский В.А. Вычислимые операции и понятие программы.

-29// .Успехи матом.наук.- 1956.- т.II, Л 4. - С.172-176.

51. Успенский В.А., СемЗноп А.Л. Теория алгоритмов: е" основные открытия и приложения. / В сб.: "Алгоритмы ь современной математике и ее приложениях, ч.1. - Новосибирск, 1982. - С.99-343.

52. Prolich A., Ehepherdaon J.С. Effective Procedures in Field Theory. //Phil.Trans.Soo. - london. - 1956. -A248. -pp.407-432.

53. Rabin U.O. On Recursively Brminera'ble "id Arithmetic Models of Set Theory. // J.Symbolio Logic. - 19?Я. -v.23. No.4. - pp.408-416.

54. Rabin M.O. Computable Algebra, (ieneral Theory and Theory of Computable Fields. // Trans.Amer.Math.Soc. -1960.' - v.95, Ко.2. - pp.341-360.

55- Vaught R.b. Sentence:;. True in All Constructive Models. // Summ.Talks Summ. Iris t.Syr,b. Log., С nell r iv. -1957. -v.l. - pp.51-55.

.6. Vaught R.L. Sentences Tn.ie in All Constructive Models.

• // J.Symbolic Logic. - 1960. - v.25, No.1. - pp.39-53-