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

г

?

д ^ . 'О 0'^ОИИСКАЯ АКАДЕМИЯ НАУК

С С* I

в ^ !

- С* >

? 5: !

. а? ;

- го

; ;

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

На правах рукописи

ВЕНЦОВ Юрий Георгиевич

УСЛОВИИ ЭФФЕКТИВНОСТИ ВЫБОРА В ТЕОРИИ КОНСТРУКТИВНЫХ МОДЕЛЕЙ

01.01.оь - математическая логика, алгеора и теория чисел

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

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

Работа выполнена в Институте математики Сибирского Отделения Российской'Академии Наук

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

Дсбрица В.П.

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

доктор физико-математических наук Белякин Н.В.

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

Защита состоится " " 1994 г. в часов на заседании

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

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

Автореферат разослан " " 1994 г.

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

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

кандидат физико-математических науг^^^у^ С.Т.Федоряев

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

АК1£альность_темы. Теория конструктивных моделей интенсивно развивающееся направление математической логики, зародившаяся на стыке алгебры и теории алгоритмов в работах А.Фрейлиха, Дк.К. Шефердсона [23], М.О. Рабина [28] и А.И. Мальцева [9] в начале 60-х годов. В [9] обобщены разрозненные методы изучения конструктивных алгебраических объектов, намечены пути дальнейшего исследования и заложены основы новой теории.

Идея, положенная в основу понятия конструктивной модели, заключается в изучении объектов вместе с их вычислимыми нумерациями и восходит к работам К. Геделя и А.Н. Колмогорова. Использование понятия нумерации позволяет с единой точки зрения взглянуть на природу вычислимости алгебраических и теоретико-модельных конструкций и объединить методы теории алгоритмов с методами алгебры и теории моделей.

В последнее время наблюдается широкое проникновение в теорию конструктивных моделей проблем и идей, возникающих в Computer Science. Так, например, вычислимое семейство частично рекурсивных функций можно, согласно А.Н. Колмогорову (см. [13J), считать семантикой языка программирования низкого уровня. При этом номера функций соответствуют программам для вычисления функций. В > современных исследованиях по Computer Science, а также при создании языков программирования высокого уровня большая роль отводится понятию абстрактных типов данных. Одна из возможных семантик этого понятия может быть определена в терминах теории конструктивных моделей. Конструктивную модель (т.е. модель, все операции и предикаты которой рекурсивны относительно фиксированной нумерации) естественно рассматривать в качестве эффективной реализации некоторого абстрактного типа данных, а вычислимый класс конструктивных моделей - как эффективную реализацию базы данных.

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

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

Понятие алгебраически корректной алгоритмической массовой проблемы, согласно [13]. определяется в рамках теории конструктивных моделей как отношение на модели, устойчивое относительно автоморфизмов. Согласно [29], это условие эквивалентно определимости отношения в языке

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

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

В настоящее время существует две школы, занимающиеся теорией конструктивных (рекурсивных) моделей. Первая, созданная А.И. Мальцевым и возглавляемая Ю.Л. Ершовым,• включает С.С. Гончарова, М.Г. Перетятькина, Н.Г. Хисамиева, В.П. Добрицу, A.C. 'Морозова и других логиков. Вторая школа, возглавляемая А. Нероудом, включает Дж. Кроссли, К. Эша, Дж. Реммела, Дж. Найт, Дж. Чизхолма и других. Как первая так и вторая школа успешно работают в направлении, которое, следуя Дж. Кроссли [22], можно охарактеризовать как анализ того, какие алгоритмы необходимо определить для той или иной теории или модели, чтобы гарантировать существование других алгоритмов или точно описать структуру модели.

В монографии Ю.Л. Ершова [8] подведены итоги первого этапа развития теории конструктивных моделей и сформулированы две основные проблемы: проблема существования конструктивизаций у модели и конструктивной модели у теории и проблема числа неэквивалентных конструктивизаций.

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

наследственно перечислимых отношений на конструктивных моделях. Эти проблемы изучались в работах С.С. Гончарова [2-71, А. Нероуда [18,27], К. Эша [15-19] и других авторов [20-22,25,30,33,34,42].

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

Цель диссертации. В диссертации разрабатывается новый подход к исследованию ряда классических проблем теории конструктивных моделей, связанный с изучением условий эффективности выбора рекурсивных объектов. Этот подход позволяет:

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

2) Сформулировать ряд дополнительных условий эффективности выбора подходящих рекурсивных объектов и решить вышеперечисленные проблемы при этих дополнительных условиях.

3) Заложить основы нового направления, связанного с выбором подходящих конструктивизаций модели по спецификациям проблем, заданных на модели.

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

теории категорий.

Ш23ная_новизна.

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

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

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

Все результаты диссертации являются новыми и обоснованы строгими доказательствами.

0Е§£™3§££ая_и_теоЕвтическая_ценность. Работа носит теоретический характер. Ее результаты и методы могут найти применение как в теории конструктивных моделей, так и в теории алгоритмов и рекурсивных функций. Полученные результаты дают решение ряда проблем из теории конструктивных моделей и могут быть использованы при чтении спецкурсов для студентов и аспирантов университетов.

Апробация. Результаты диссертации докладывались и анонсировались в разное время на логических семинарах ИМ СО РАН, НГУ, МГУ, КазГУ, на Всесоюзной конференции по логике (Алма-Ата, 1991), Межреспубликанской конференции по математической логике (Казань, 1992), Международной конференции по логике (Варна, 1990), Международном конгрессе по логике, методологии и философии науки (Уппсала, 1991), Логическом Коллоквиуме Ассоциации Символической Логики (Весзпрем, 1992), Логическом Семестре (Варшава, 1991), Логическом Коллоквиуме АСЛ (Киль, 1993), 5-й Международной

Азиатской Логической конференции (Сингапур, 1993).

П^олшации. основные результаты диссертации опубликованы и анонсированы-в работах автора [30-44].

Стр2кт£ра_5иссертации. Диссертация состоит из введения, трех глав, приложения и списка литературы. Названия глав следующие: "Эффективно перечислите отношения и эффективно автоустойчивые конструктивные и позитивные модели", "Вычислимые классы конструктивизаций моделей бесконечной алгоритмической размерности", "Эффективный выбор конструктивизаций и рекурсивная совместность проблем на конструктивных моделях". Объем диссертации - 180 страниц, список литературы включает 44 наименования.

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

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

При определении понятий, используемых в диссертации, автор придерживался терминологии из монографий [8,11].

Через Соп(Л), Роз{М) обозначим, соответственно, класс конструктивизаций и класс позитивных нумераций модели М. Пусть Т>у(Л), обозначает атомарную диаграмму модели Л

относительно конструктивизации V и позитивную диаграмму модели Л относительно позитивной нумерации ц, соответственно. Отношение (позитивно) -определимо на модели, если оно совпадает с подмножеством, определяемым на модели некоторой (позитивной) рекурсивной -формулой языка

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

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

отношений занимались многие авторы. К.Эшем и А.Нероудом [18] в предположении разрешимости 1-диаграммы модели с дооавленным к сигнатуре новым предикатным символом К доказано, что отношение на модели, соответствующее К, наследственно рекурсивно перечислимо тогда и только тогда, когда оно -определимо в модели с конечным набором параметров.

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

В [19,21] К.Эшем, Т.Сламаном, Дж.Найт, М.Манасси и независимо Дк.Чизхолмом изучается понятие относительно перечислимого отношения, т.е. отношения, изоморфный образ которого рекурсивно перечислим относительно диаграммы любой модели (не обязательно конструктивизируемой), изоморфной данной. Применение форсинга позволило доказать эквивалентность этого понятия -определимости с конечным набором параметров.

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

Сформулируем некоторые определения и теоремы.

Пусть отношение К на конструктивизируемой (позитивной) модели М устойчиво относительно автоморфизмов. ОПРЕДЕЛЕНИЕ 1.1.1. Отношение К равномерно эффективно перечислимо в классе конструктивизаций (позитивных

нумераций), если существуют конечный набор параметров аеЛ и рекурсивный оператор перечисления Т такие, что для veCon(Л)

(г>бРоз(Л)) по перечислению ОЛЯ,а) {Т)^{Л,а)) оператор 7

перечисляет множество

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

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

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

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

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

В диссертации используется определение экстенсиональной операции, аналогичное соответствующему определению из [26]. ОПРЕДЕЛЕНИЕ 1.2.2. Отношение 72, определенное на модели,, имеющей позитивную нумерацию, (слабо) програмно перечислимо в классе позитивных нумераций, если существует экстенсиональная о.р.ф. <р такая, что (при некотором конечном

наборе элементов а модели) для любой позитивной нумерации г^ модели имеет место равенство

%><!) = <*>

ОПРЕДЕЛЕНИЕ 1.2.3. Отношение Л, определенное на

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

такая, что (для некоторого конечного набора параметров а из модели) выполнены следующие условия:

а) ф определена на любом рекурсивно перечислимом индексе

конструктивизации г^ (и у^-номерах т элементов набора а)

произвольной модели Л языка С, причем ф(1) (ф(1,т)) есть клшшевский номер некоторой о.р.ф.;

б) если V. является конструктивизацией исходной модели (т-•

^-номера элементов из а), то о.р.ф. </ф(1 йр есть

характеристическая функция множества v~í(R). ТЕОРЕМА 1.2.4. Отношение на модели, имеющей позитивную нумерацию, (слабо) программно перечислимо в классе позитивных нумераций тогда и только тогда, когда оно позитивно ^-определимо на модели (с конечным набором параметров).

Доказательство этой теоремы существенно опирается на результаты из [12,26].

Следующее предложение, показывает, что условие всюду определенности функции выбора в определении 1.2.3 существенно.

ПРЕДЛОЖЕНИЕ 1.2.5. Существуют конструктивизируемая модель Л и отношение К на Л, такие что для некоторой ч.р.ф. ф и любой конструктивизации г^ модели Л значение ф(1) определено и

"фШ^Г^' но к не ^-опРедалимо в -К-

■ Аналогично доказывается следующее предложение. ПРЕДЛОЖЕНИЕ 1.2.6. Существует модель Л, имеющая позитивную нумерацию, и отношение К, для которого существует ч.р.ф. ф такая, что для любой позитивной нумерации vi модели Л выполнено условие причем Я не позитивно

^-определимо в А.

Для класса программно перечислимых отношений на конструктивных моделях имеет место следующая теорема. ТЕОРЕМА 1.2.7. Отношение, определенное на конструктиви-зируемой модели, (слабо) программно рекурсивно в классе конструктивизаций тогда и только тогда, когда оно

¿^-определимо в модели (с конечным набором параметров).

Доказательство этой теоремы использует результаты из [14,243.

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

Понятие автоустойчивости впервые определил А.И. Мальцев в [Ю]. Автоустойчивые (рекурсивно категоричные) модели привлекали внимание многих авторов [2,3, б, 15-19, 21, 22, 30, 32-34, 42].

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

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

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

ОПРЕДЕЛЕНИЕ 1.3.1. Конструктивизируемая (позитивная) модель Л называется эффективно автоустойчивой в классе конструктивизаций (позитивных нумераций), если существуют

конечный набор параметров а из Л и эффективный оператор перечисления 7 такие, что для любых

€ Сап(М) е Роа(М))

по перечислению прямой суммы диаграмм

гул,а) ® гул,а) (Е>+(Л,а) ® 1>+(Л,а)) 7 перечисляет график о.р.ф. для которой у°/=ОоЦ при подходящем автоморфизме а.

Следующие две теоремы описывают классы эффективно

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

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

Вторая глава посвящена изучению конструктивных моделей бесконечной алгоритмической размерности. Алгоритмическая размерность конструктивных моделей исследовалась многими авторами [2-7,10,30-33,37-39]. А.И.Мальцев в [Ю] построил пример неавтоустойчивой группы и показал, что для

любой конструктивизируемой модели Л.

Для большинства моделей алгоритмическая размерность принимает значение либо 1 либо и. С.С.Гончаров [4,7] доказал, что для любого пеш существует модель такая, -что (Ит^Лп) = п.

Конечная алгоритмическая размерность соответствует наличию у модели конечного оазиса в классе всех конструктивизаций.

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

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

.Частично это показано в [31,33], где строится конструктивная модель бесконечной алгоритмической размерности, не имеющая бесконечных вычислимых классов попарно неавтоэквивалентных конструктивизаций.

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

содержащих со неавтоэквивалентных конструктивизаций.

Основной результат первого параграфа второй главы заключается в построении такой модели. В главе представлен новый метод, базирующийся на методе приоритета с бесконечными нарушениями, разработанный в [4,5] и применяемый в [31,32].

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

В [2,3] определены классы неограниченных и ветвящихся моделей. Как известно, классы конструктивизаций таких моделей эффективно бесконечны, следовательно, их алгоритмическая размерность равна и. Позднее автором [30] обобщены теорема о ветвящихся моделях и само понятие ветвления.

С.С.Гончаров поставил вопрос об описании некоторого класса моделей бесконечной алгоритмической размерности, содержащего как ветвящиеся так и неограниченные модели. Естественный подкласс К моделей, описываемый во втором параграфе, включает в себя оба эти класса.

Из результатов первого параграфа следует невозможность конструктивного описания класса моделей бесконечной алгоритмической размерности.

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

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

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

В классе формул языка ш выделим рекурсивные

гк * *

2а-формулы для а<ь£ . Отношения определяемые этими формулами

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

Семейство проблем 2=(7ео,7г1,...) на Ж называется вычислимым, если существует последовательность П=(Фо,Ф1,...) рекурсивных 2а-формул языка такая, что в Л выполнена

эквивалентность

{Л± - Ф1) & (Ф± К±) для всех Кш, причем, существует рекурсивная функция /, для которой /(1) есть геделев номер формулы Ф^

Пусть Рг(А) - класс всех проблем в Л, рекурсивных при подходящих конструктивизациях и выразимых рекурсивными формулами языка Сш Основной вопрос, рассматриваемый в

третьей главе заключается в следущем. Существует ли эффективный способ построения по проблеме КеРг(Л) конструктивизации v£Con(Л), относительно которой 72 рекурсивна?

Пусть % с Соп(Л) - вычислимый класс конструктивизаций, 2 с Рг(Л) ~ вычислимое семейство проблем на Л.

Будем говорить, что задача выбора (Г(2,тс) имеет' эффективное решение, если существует рекурсивная функция g, для которой рекурсивно при всех Ко), 72^2,

В [41 ] строится пример модели Л и семейства § вычислимых классов конструктивизаций Л таких, что для каждого вычислимого класса существует вычислимое семейство

2сРг(Ж), состоящее из рекурсивных 2г-формул, такое, что задача выбора (Т(2,о) не имеет эффективного решения.

С другой.стороны, этот же результат справедлив в любом

бесконечномерном конструктивизируемом векторном пространстве У,-где в качестве 2 берется некоторое вычислимое семейство рекурсивных -формул, выражающих линейную зависимость п векторов для соответствующих п<ш.

В то же время, как видно из [27], для каждого такого 2 в у эффективно находится вычислимый класс о, для которого <1(2,а) всегда имеет эффективное решение.

Пусть Р ш Я принадлежат Рг(Л). Назовем Рид рекурсивно совместными, если существует щСоп{Л) для которой т)~1(Р) и г]"1 (б) рекурсивны. В противном случае будем говорить, что Р и <Э рекурсивно несовместны. Аналогично определяется рекурсивная совместность любого вычислимого семейства проблем на Л. Следующая теорема дает одно достаточное условие при котором задача выбора ®(2,а) не имеет эффективного решения.

ТЕОРЕМА 3.1.1. Пусть Л- конструктивизируемая• модель языка С, имеющая рекурсивно несовместные проблемы Р и <2 из Рг(Л), тогда существует вычислимое семейство проблем 2=(7£о ...), для которого выполнены следующие условия:

1) для каждой К± существует v(.Con{Л) такая, что множество V'1 {К±} рекурсивно;

2) для любого вычислимого класса а^Соп(Л) задача выбора (5(2,о) не имеет эффективного решения.

СЛЕДСТВИЕ 3.1.2. Пусть Р и О - проблемы из Рг(Л), тогда следующие утверждения эквивалентны:

(I) Р и Я рекурсивно совместны в Л;

(II) для любого вычислимого семейства 2=(Фо,Ф1,...) рекурсивных формул языка Си ш такого, что

1<ш} = {Р,(Э}

существует вычислимый класс о конструктивизаций модели Л такой, что задача выбора <Г(2,а) имеет эффективное решение.. СЛЕДСТВИЕ 3.1.3. Пусть Р0,• ••.Рп принадлежат Рг(Л), -следующие условия, эквивалентны:

(I) множество проблем {Р1.....Рп> рекурсивно совместно;

(II) существует для которого проблемы

Р., (Р± » ... « « Р^ х ... к Рп) рекурсивно совместны.

Пусть 2=(К0,К ,...)-вычислимое семейство не пустых проблем из Рг{Л). Рассмотрим

зк

2 = Е и Щ. X ... х к ; п<ш}. о ХП

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

ТЕОРЕМА 3.1.6. Семейство 2 рекурсивно совместно тогда и только тогда, кбгда для любого вычислимого семейства рекурсивных формул 0=(Ф1: 1<ш) языка ш такого, что

множество П-*1 = (Ф^: Коз} содержит, по крайней мере, две различные проблемы и С?** с £*, существует вычислимый класс о с Соп(Л), при котором задача выбора <Г(П,о) имеет эффективное решение.

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

ТЕОРЕМА 3.2.1. Пусть Л - конструктивизируемая модель языка С. Следующие условия эквивалентны:

(1) для любого вычислимого семейства проблем 2 из Рг(Л) существует вычислимый класс конструктивизаций о с Соп(Л) такой, что задача выбора <Е(2,о) имеет эффективное решение.

(И) любое вычислимое семейство проблем из Рг(Л) рекурсивно совместно.

Являясь, в некотором смысле, аналогом известной теоремы Райса, теорема 3.2.1 утвервдает, что язык

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

В связи с этим возникает достаточно важная, по мнению автора, задача о нахождении таких фрагментов языка

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

ЛИТЕРАТУРА

1. В. В. Вьюгин, 0 некоторых примерах верхних полурешеток вычислимых нумераций, Алгебра и логика 13, Ji5 (1973) 512-529.

2. С.С. Гончаров, Автоустойчивость моделей и абелевых групп, Алгебра и логика, 19, JH (1980), 23-44.

3. С.С. Гончаров, В.Д. Дзгоев, Автоустойчивость моделей, Алгебра и логика, 19, J69 (1980), 45-58.

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

5. С.С. Гончаров, Вычислимые однозначные нумерации, Алгебра и логика, 19, Мб (1980), 507-5116. С.С. Гончаров, А.Т. Нуртазин, Конструктивные модели полных разрешимых теорий, Алгебра и логика, №2 (1973), 125-142.

7. С.С. Гончаров, Проблема числа неавтоэквивалентных конст-руктивизаций, ДАН СССР, 251, №г (1980), 271-274.

8. Ю.Л.Ершов, Проблемы разрешимости и конструктивные модели. М. .-Наука, 1980.

9. А.И. Мальцев, Конструктивные модели I, УЫН, 16, Лз (1961 ), 3-60.

10. А.И. Мальцев, 0 рекурсивных абелевых группах, ДАН СССР, 146, (1962), 1009-1012.

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

12. В.А. Успенский, Об операторах перечисления, ДАН СССР йЮЗ (1955) 773-776.

13- В.А. Успенский, А.Л. Семенов, Теория алгоритмов: основные открытия и приложения, М., Наука, 1987.

14. Г.С. Цейтин, Алгоритмические операторы в конструктивных полных сепарабельных метрических пространствах, ДАН СССР, #128 (1959), 49-52.

15. G.J. Ash, Stability of recursive structures in arithmetical degrees, Annals of Pure and Applied Logic, 32 (1986), 111-135.

16. C.J.Ash, Reoursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Transactions of the Amerioan Mathematical Society, 298, Я2 (1986), 497-514.

17. C.J. Ash, Categoricity in hyperarithmetical degrees, Annals or Pure and Aplied Logic 34, Jfel (1937) 1-14.

18. C.J. Ash, A. Ileroda, Intrinsically recursive relations, Aspects or Effective Algebra, Proc. Conf. Monash Univ., Australia, 1981, 26-41.

19. C. Ash, J. Knight, M. Manasse, T. Slaman, Generic copies of countable structures, Annals of Pure and Applied Logic, 42, 1989, 195-205.

20. J. Chisholm, The complexity of intrinsically r.e. subsets of existentially decidable models, The Journal of Symbolic Logic 55, #3 (1990).

21. J.Chisholm, Ph.D. dissertation, University of Wisconsin, Madison (1990).

22. J.N. Crossley, A.B. Manaster, M.F. Moses, Recursive ca-tegoricity and recursive stability, Logic Paper, Monash University, M9 (1983).

23. A. Frolich, J.C. Shepherdson, Effective procedures in field theory, Phil. Trans. Royal Soo. London, A 248 (1956), 407-432.

24. G. Kreisel, D. Lacombe, J.R. Shoenfield, Partial recursive functionals and effective operations, in Constructivity in Mathematics (Heyting ed.), North-Holland, 195-207.

25. M.S. Manasse, Techniques and counterexamples in almost categorical recursive model theory, Ph.D. dissertation, University of Wisoonsin, Madison, 1982.

26. J. Myhill, J.C. Shepherdson, Effective operations on partial recursive functions, Zeit. Math. Log. Grund. Math. 1 (1955) 310-317.

27. A. Nerode, J. Remmel, Recursive theory of matroids 2, South-East Asian Conference on Logio, North-Holland, 1983, 133-184.

28. M.O. Rabin, Computable algebra, general theory and theory of computable fields, TAMS, 95, JK (1960), 341-350. 29- D. Scott, Logic with ¿enumerable long formulae and finite strings of quantifiers, in: J.W.Addison, J.Henlein and A.Tarski. eds., The Theory of Models, North-Holland, Amsterdam, 1965).

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

30. Ю.Г. Венцов, Алгоритмические свойства ветвящихся моделей, Алгебра и логика, 25, М (1986), 369-383.

31. Ю.Г. Венцов, Семейство рекурсивно перечисликых множеств с конечными классами неэквивалентных однозначных вычислимых нумераций, Вычислительные системы, J6120 (1987), 105-142.

32. Ю.Г. Венцов, Неравномерная автоустойчивость моделей, Алгебра и логика, 26, Л66 (1987), 422-440.

33- Ю.Г. Венцов, Об алгоритмической размерности моделей, ДАН СССР, 305, J61 (1989), 21-24.

34. Ю.Г. Венцов, Проблема эффективного выбора для отношений и сводимостей в классах конструктивных и позитивных моделей, Алгебра и логика 31, №£ (1992), 101-113.

35. Ю.Г. Венцов, Задача эффективного выбора конструктивиза-ций и рекурсивная совместность проблем на конструктивных моделях, Алгебра и логика, 31, ЛИ (1992), 3-20.

36. Ю.Г.Венцов, Проблема эффективного выбора конструктивиза-ций, Труды Института математики СО АН СССР, Издательство ИМ СО РАН, 1993, Т.25, 35-40.

37. Ю.Г. Венцов, Эффективные операции выбора на конструктивных и позитивных моделях, Алгебра и логика, т.32 (1993) №1, 45-53.

38. Ю.Г. Венцов, Вычислимые классы конструктивизаций моделей бесконечной алгоритмической размерности, Алгебра и логика, т.33 (1994) J61, 37-75.

39. Ю.Г. Венцов, Конструктивные модели регулярно бесконечной алгоритмической размерности, Алгебра и логика, т.33 (1994)

137-148.

40. Yu.G. Ventsov, A problem of effective choice of const-ructivizations, Abstracts of the 9th International Congress of Logic, Methodology and Philosophy of Science, Uppsala, 1991, 67.

41. Yu.G. Ventsov, On effective choice of constructivi-zations, Siberian Advances in Mathematios 2, Ji1 (1992), 1-7.

42. Yu.G. Ventsov, Effectively recursive relations and effeotive categorioity, Abstracts of the 1992 European Summer Meeting of the ASL, Veszprem, 1992, 48.

43. Yu.G. Ventsov, Infinite and Effectively Infinite Algorithmic Dimension of Recursive Models, Abstracts of the Fifth. Asian Logic Conference, Singapore, 1993, 56.

44. Yu.G. Ventsov, Effectively Infinite Algorithmic Dimension of Recursive Models, Abstracts of Logic Colloquium'93, Keele, 1993, 1.

Отпечатано на ротапринте Института математики СО РАН 630090, Новосибирск-90, Университетский проспект, 4

Подписано к печати 06 .¿ty.94 Формат бумаги 60x84 1/16 • Заказ

Объем 1,25 п.л. ,1,125 уч.-изд.л. Тираж 100 экз.