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

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

к

Специализированный Совет Д G02.23.01

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

. ФЕДОРЯЕВ Сергей Тимофеевич

УДК 510.53:510.67

• ЫТУКТУРНЫЕ СВОЙСТВА АЛГЕБРАИЧЕСКОЙ .

сводимости КОИСТРУКТИВИЗАЩЙ

и ' » -

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

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

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

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

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

профессор'С.С.Гончаров Официальные оппоненты - доктор физико-математических наук, ' профессор Д.М.Смирнов

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

- Б.М.Хусаинов . - "

• •

«

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

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

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

Автореферат разослан " 199Ш .

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

ВИГ-СКосырский

Бурное развитие теории конструктивных моделей, ттоследовашев за основополагающей работой л.И.Мальцева "Конструктивнее алгебры" и визванное прежде всего наличием многочисленных алгоритмических массовых проблем алгебры и теории моделей,- а а последние год! и задачами создашь логических систем программирования (где теория конструктивных м' челей составляет математический Сезис ьбстрэт.т-ных типов данных и семантики языков программирования с абстрактными типами данный) привело к ряду ваащейших результатов и постановке новых интересных проблем. К их числу относится и проблема изучения различных типов сводимостей конструктивизаций и соотношений между ними. . •

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

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

Классическими и наиболее изученными являются , автосводшоеть и сводимость конструктивизаций по Колмогорову (2,8,11] (обозначим эти отношения сводимости соответственно'' , ). В настоящее 'время в теории конструктивных моделей , имеется уже значительное число результатов,-связанных с изучением автосводимости и сеодимости конструктивизаций по Колмогорову, и прежде всего с проблемой единственности и числа конструктивизаций относительно этах сводаюстей [Г-12,15,17-19,213.

Развитие теории конструктивных моделей, возможность применения (через понятие эффективности t:a модели) развитей теорда алгоритмов к исследованию разрешимости многочисленных, алгоритмических массовых проблем алгебры я теории моделей, т~ких кр". проблема равенства, сопряженности элементов группы, проблема алгебраической

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

Приведем здесь основное понятие алгебраической сводимости. Конструктивизацня v модели Ш алгебраически сводится к конструк-тдпизэции (.i этой же модели (символически v ц }, если всякое устойчивое отношение модели ал , разрешимое при . конструктивизашш ^ является разрешимым и при г' .

Часто нас интересуют конкретные алгоритмические маейовые проблемы ^тримзры которых приведены ваше) , а также класс'« йроб-лем, местность которых- ограничена. Поэтому мы определяем ограниченные алгебраические сводимости, которые служат "апироксймадпей" для алгебраической сводамости. Рассматривая только m-месйшо устойчивые отношения при. m < п , получаем понятие п-а.Тгедраичес-кой сводимости (символически ).

Симметризация каадого из введенных отношений" сводййобти приводит к своему с/ношению эквивалентности. Две конструк'ШЕизации модели Sí называются . ^.-эквивалентными, если каждая ;йз 'них А-сводится г. другой, а число классов ^-эквивалентных конструктивиза-ций модели ЕЯ называется ^.-размерностью данной моде.йи Щ обозначается X-dim{$l'), \ € {/^.Д^.П.^ЙД}. Модель'■ Х-разыерности I называется ^-устойчивой.--' »

Тагам образом, для кгчетруктивизирупмой модели £1 определены • алгоритгтческие размерности (см.[II]): алгебраическая, програм- ■ иная, равномерная, колмогоравская, и авторззмериость. причем выполняется следущэя .сг:стека нестрогих нер&венота:

ñ^-dlmim) $ П-dmiTi) $ Р-П1п{11) í A-dtR(a) С-íiir.(:,(,.

.Кс.тест. .iifio возникает: сшдукззэ вонр^н, гкетавденнж в III] В.А.Уси-нскиа :

1) Проблема соотношений алгоритмических размерностей:

а) Бывают ли конструктивизируемые модели, для ко^рых один из этих знаков можно заменить на "<" ?

б) Когда знаки Можно заменить на знаки я=" ?

2) Проблема сйектрэ алгоритмических размерностей: какие .таборы чисел могут "й^ь наборами алгоритмических размерностей алгебраических систем: алгебраической, программной, равномерной, колмогоровской и а^ор&змерностй ?

Первый нетривиальный пример соотношений -пгоритмических размерностей, а также полное реиение проблем спектра и соотношений алгоритмических размерностей для абелевых групп одного класса били получены С.С.Гончаровым [6]. В общем случае • проблема соотношений алгоритмических размерностей алгебраических сис 'ем была решена Б.М.Хусаиновым [13,141. В настоящей диссертации проб-леш спектра и соотношений алгоритмических размерностей исследуются для классов классических математических объектов.

Каждое из введенных отношений сводимости задает на совокупности Н(5Я) всех конструктивизаций модели 5Л <федпорядск. Тем се-?дим на множеот^е классов А,-эквивалентных конструктивизаций ,и вообще, А.-эквивалентных нумераций) модели Э!. возникает частично упорядоченное множество относительно" К-с одимости, которое будем называть структурой, х-сводимости.модели 31 .

Таким образом, для произвольной модели 5Я определено понятие структуры алгебраической сводимости. Содержательный смысл алгебраической сводимости и структуры относительно этой сводимости состоит в следующем. Для любой конструктивизашш V с 11<5!1) можно ЕЫбрать не Солее чем счетную',' ..арактеристическую" совокупность ву с БаШ) алгоритмических массовых проблем так,-что выполняется следующее сЬойство, определяющее отношение зависимости гткой совокупности алгоритмически?. массовых проблем от другой.

1№ЩЯ0КЕНИЕ I..Пусть . г>,ц е Н(В1) , тогда следующие условия эквивалентны: '

(2) все отнесения из совокупности ву ц-разрешимы,

(3) для лкбой . конструктивизаияи модели 951 разрешимость псех отношений совокупности 8,. влечет разрешимо-гь все", отношений из

Таким образом, алгебраическая сводимость конструктивизаций

означает да что инор, как-зависимость одной совокупности ву алгоритмических массовых проблем от другой е ; элемент структуры алгебраической сводимости однозйачно определяется некоторой- "характеристической" совокупностью в , её выбор также однозначен с точностью до естественной эквивалентности ; а структура; алгебраической сводимости отражает все зависимости между; совокупностями алгоритмических массовых проблем, характгризующих накое-тбо эффективное представление рассматриваемой модели; и описывает в-определенном смысле внутреннюю сложность самой модели1., этим1, объясняется интерес к изучению этого объекта.

Заметим, что зависимости отдельных совокупностей алгоритмических массовых проблем для конкретных алгебраических систем исследовались, мне или авторами. В булевых алгебрах ДД'еммел- изучал зависимости некоторых совокупностей проблем .из. множества; атомов и идеалов Фреше Р , сс < [17-19], ^ в классе линейных порядков некоторые зависимости-для отношения соседей, блок.оэноше*шя<и-отношений предшествования и следования получены М-МЬзесом.;,. от-цоше'иия ) линейной зависимости п элементов, бесконечномер-

ного векто; чого пространства , отношения алгебраической

зависимости п элементов алгебраически замкнутого поля; и соответствующие отношения зависимости для систем. <Ц-,а1>- с'операцией замыкания рассматривались в работах [8-10,15-16 ]<д. Ол-наг , в" целом для структур алгебраической сводимости;было известно лишь следующее: так как автосводамость конструктишзаций эквивалентна их автоэквивалентности, то известные примера¿жестких моделей конечной аг 'оразмерности [4] показывают, что антицепь счетной "или любой конечной мощности является структурой! алгебраической сводимости подходящей жесткой модели. '

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

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

На осн'зе введенных автором теоретико-модельных понятий ав-тскорф. >Я п-связанности, сильно однородного отношения и некото-

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

ТЕОРЕМА 1. Если модель 14 имеет алгоритм автоморфной ''п+1)-связанности, и отношение автоморфной п-связашюсти разбивается на конечное число с.льно однородных отношений, то алгебраическая сводимость конструктивизаций модели ЗЯ эквивалентна п-алгебраи-ческб* сводимости.

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

ТЕОРЕМА 2. Справедливы следующие утверждения:

1) Для всякого натур льного.числа к > л существует уноид 31 такой, что алгебраическая сводимость конструктивизаций экеп-валентна 1-алгебраической сводимости и

Ф1-йШ('51)= = 21с < &-й1т{91) = и.

2) Для всякого натурального числа к > 2 существует модель 1Я такая, что алгебраическая сводимость конструктивизаций Ж зквива-лентна 1с-алгебраической сводимости и для любого ш < к

Лп-с!Ш(ЗК)= ШИ < й1,-с21пг^2Л)= й^-Ши.Л) = к+1 < и.

3) Существует модель ^ такая, что для любого к ? 1

АусИякМН к-и < Дш-(3{»г(4Д).= Л-й4я(а)= со.

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

Во многих классических алгебраических системах ал легко обнаружить среди всех проблем и5 £1 (ВО алгоритмические массовые лроб-лемы, имеющие, "линейную" зависимость. Таков.., нзпр м ухе упо-минавшиеся1 отношения'соответствующих зависимостей п-элементов в векторных пространствах, полях к системах с операцией замыкания.

с

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

ТЕОРЕМА 3. Всякое конечное линейно лорядоченное множество (линейно упорядоченное множество Типа -он ) является структурой алгебраической сводимости подходящей модели. •

Заметим, что наименьший и наибольший элемента структуры алгебраической сводимости произвольной модели $л выделяют границы между конструктивизациями по числу разрешимых алгоритмических массовых проблем, т.е. являются • соответственно "наилучшим" и "наихудшим" эффективными представлениями модели ЗЛ . Поэтому с точки зрения нахоздешш "наилучшего" эффективного представления является принципиальным вопрос существования наибольшего и наи-мэньшзго элементов в структуре алгебраической сводимости модели 101 . До настоящего времени не были известны примеры моделей, структура алгебраической сводимости которых имеет наибольший элемент, но не имеет наименьшего элемента. В..диссертации доказывается, что 'для всякого натурального <шсда п п-симплекс (т.е. верхняя полуреиетка, получающаяся из булевой алгебры 2П+1 удалением наименьшего элемента) является структурой алгебраической сводимости относительно позитивных нумераций подходящей модели.

В третьей главе диссертации изучаются независимые совокупности • алгоритмиче, лак массовых проблем и, связанные с этим* проблемы спектра и. соотношешй алгоритмических размерностей,.. Совокупности Т1 , и £ й II М, алгоритмических массовых, проблем модели ЗЛ независимы, если существуют коцртруктадздзацэд' V, модели такие, что все проблемы из. гу-разрешимы в том и только том случае, когда {=/ .

Как уже отмечалось ' структура алгебраической, сводимости произвол--ной модели Зй отражает все зависимости кезэду "характер ристичоскими" совокупностями 6г, с st(Ш) алторитмич ских массовых нро.лем. Поэтом" сначала исследуется, какие модели предъявляют все возможные такие зависимости. Другими словами, рассма^рива-ется следую. ,й вопрос:-гчсколько богат долен бить язык и класс моде.)'^ для это^о я.-шкз, чтобы структуры алгебраической сводимо-

ь

сти для моделей данного класса указывали все структуры, реализукн щиеся в качестве структур алгебраической сводимости ? Оказывается, в этом смысле класс частично упорядоченных множеств аздязтся полным, и бо "зе того, имеет место следующая

ТЕОРЕМА 4. Структура алгебраической сводимости (программ .ой, равномерной, колмогоровской и автосводимости) любой модели Й конечной сигнатуры изоморфна структуре алгебраической сводимости (соответственно программной, равномерной, колмогоровской и автосводимости) подходящего частично упорядоченного множества 831 , причем эти изоморфизмы могут бить заданы факторизацией одного отображения 5 : Н(ЗЯ) —> Н(?1) по соответствующему отношению эквивалентности.

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

Далее, используя идеи ветвимости модели [1,7], найдено условие рекурсивной несовместности двух последовательностей отношений конструктивной модели, которое, обеспечивает существование констг руктиЕизации, при которой разрешат все отношения одной последовательности и неразрешимы все отношения другой. Доказательств^ проводится методом приоритета.

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

ТЕОРЕМА 5. Пусть В дистрибутивная решетка с относительным*, дополнений!, нулем и бесконечным числом атомов. Если £> допускает' конструктивизацию с разреши?,-шм идеалом Фреше, то структура алгебраической сводимости решетки В тлеет счетную ширину.

Полное регзние проб-йем спектра и соотношений.алгоритмических размерностей, а т.акже критерий алгоритмической устойчивости для дистрибутивных решеток ■< Р ¥ > с относитильнаш дополнениями и нулем г языке с идеалом Фрваэ Р дает следующая

ТЕОРЕМА 5- Для коиструктивиз!груемой дастркЯривной решетки < IV? > с откопптолькша дсполнаништ а нулем слодуташе у слоям гжчпвадек ¿и:

Я) решг :;-:а < Ь\Т а яо злгеОпамРь.д: уото^.зз'

(Г., алгебраическая размерность < > равна и ,

<3) решетка < Ъ,Е > имеет бесконечно много атомов.

,СЛЬТ;СТВ;Ш I. Для дистрибутивных решеток < > с относительны«'.'. дополнениями и ну.^м алгебраическая, программная, равномерная размерности и зет "»размерности совпадают. Спектр этих раз-' мерностей состоит из О, I и ш , а гпектр колмоголовской размерности состоит из О, I и 2Ш.

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

1г:о?ЕМД 7. Пусть лилейный порядок и длины блоков не ограничены в совокупности. Если а допускает конструктивизацию с разрешимым ол;>к г тнои. ,нием, то структура алгебраической сводимости лглейк го порядка -И имеет счетную ширину.

Заметим, что отедзаться от условия неограниченности в совокупности длин всех блоков линейного порядка, вс обще говоря, нельзя. Существует /идейный порядок и; , ' для которого структура алгебраической сводимости является трбхэлемент'чгм линейно упорядоченным множеством, Таким образом, линейный порядок 51 воибще не имеет независимых совокупностей алгоритмических массовых проблем. :.роме того, получается довольно неожиданное соотношение а. гори.-шческих размерностей в классе линейных порядков ' •

А -сИт(^) < ('•!!) = ш .

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

ТЕОРЕМА 8. Для конструктивизируемого рассеянного линейного порядка с > следующие условия эквивалентны:-

(1) <&,8 > но алгебраически устойчив,

'(2) алгебраическая размерность < ii.fi > раЕна ш ,.

(2) у $1,2 > бесконечен.. ,

СЛЕДСТВИЕ 2. 'Лпя рассеянных линейных 'порядков <* 91,^ -> алгеб-. раическая , программная, равномерная и авторазмерность совпала..г. Спектр этих размерностей состоит у. О, I и 'и , .а спектр ¿солмо-: оровской размерности состоит из и, 1, Ь) и 2й.

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

< 5),В. > получена в следующей теореме.

ТЕОРЕМА 9. Для конструктквизаруемог^ шшейного порядк"

< 5i.fi > следующие условия эквивалентны: '

(1) «г'Я.В > алгебраически устойчив,

(2) линейный порядок < Я,В > т.;ет порядковый тип .

для некоторых е ш , »л ш , к,? 0°, п с К,

(3) < а,В > автоустойчив.

СЛЕЦГТВИЕ 3. Для произвольного линейного порядка 21, В > алгебраическая , программная, разномерная устойчивости и автоустойчивость эквивалентны.

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

Основные результаты диссертации опубликозаны в работах автора [22-28] и докладывались на семинарах "Алгебра и логика", "Теория нумераций" и "Конструктивные модели" при Новосибирском государственном университете и Институте математики СО 4К СССР, на л Всесоюзной конференции по математической логике (г.Алма-Ата, 1990 г-.), на семинаре кафедры алгебры Казанского уж.зерсктета.

Автор выракает ^глубокую признательность своему научному руководителю, доктору физико-математических наук, профессору С.С.Гончарову за постоянное внимание к работе и многочисленные полезные обсуждения.

ЛИТЕРАТУРА

1. Венцез Ю.Г. Алгоритмические свойства ветвящихся моделей //Алгебра к логика.- 1986,- Т.25, X 4.- С.369-383.

2. Гончаров G.G. Счетдае булева алгебры. - Новосибирск.; Наука, 1983. - 176 с.

3. Гончаров C.G. Автоустойчивость моделей к абелевых групп //Алгебра и логика.- 1980.- Т.19, Ä 1. - С.23-44.

4. Гончаров С.С. Проблема числа неавтоэквивалентных констру-хтквизрций //'Алгебра и логика.- 1980. - т.19, » в. - 0.621-6з9.

5. Гончаров С.С. Группы с конечным числом ионструктивиза-ций //ДАН СССР. -I98I. -Т.256, № 2.- С.269-272.

6. Гончаров С.С. Алгоритмическая размерность абелевых групп //17-ая Всосойз. алгебраическая конф., Минск, сент. 1983г. •. Тез.докл.- Минск,- 1933. -С.51.

7. Гончаров С.С., Дзгоев В.Д. Автсустойчпвость моделей //Алгебра и логика.- Г980- - Т.19, & I,- С.45-58.

8. Ершов й.Л. Проблемы разрешимости и конструктивные мо^з-;ч.-М.: Наука, 1980.-'416 с.

9. Ерсюз П.Л. Алгоритмические проблем; в теории полей (положительные аспекты) //Справочная книга по математической логике. Ч.З. - !.!.: Наука, 1982. - С.26Э-253.

10. Мальцев А.И. О рекурсивных абелевых группах //ДАН СССР. -. I9S5.- Т.146, Й 13. - Ь.1009-1012.

П. Успенский B.Av, Семенов A.A. Теория алгоритмов- еЗ основные открытия и приложения //Алго; нтмы в современной математике и еб приложениях, 4.1. - Новосибирск, 1982. - С.99-342.

12. Хусоинзв Б.М. Сильно эффективные унары и неавтоэквивалентные конструктивизации //Ыеквуз. сб.науч. тр. Некоторые проблемы дифференциальных ¿фавноний и дискретной математики.- Новосибирск: НГУ, .986. - С.33-44.

13. Хусаиноз Б Y. Об алгоритмической размерноои. уна^ов //Алгебра и логика.- I9S3. Т.2/, ^ 4.- С.479-494.

14. Хусаинов Б.М. О различаемо^™ алгоритмических ра-чвров алгебр //10-ая Всесокс. конф. по мчтеч. лоьле, Алма-Ата, нояб. 1990 г. : Тез. докл.- Алма-Ата, 1990.- С.160.

15. Hetakides G., Herede A. Recursion theory on fields and abstract clöxjende ice //<J. Algebra.- 19SO.- v.6r, Ji 1.- ^.'36-5?.

16. Nerode a., Rernsl 0. Recursive theory or ' tr.at.ro:da Л. //

Ргоз. Southeast Asian СояГ. on Logic, tiew York.- North-Holland, 1983.- p. 133-184.

17. Reirm&l J.5. Recursive isomorphism types of re^rrsiva Boolean algevras //«J.Symbol „log. - 1331.- v.46. й 3.- p.572-594.

18. Remmel J B. Recursive Boolean algebra-, with, rscur:. ive atoms. //J. Symbol.log.- 1981.- v.46, » 3.- p.595-61^.

19. Reffimsl J.B. Recursive Boolean algebras //Handboo5c of Boolean algebras.- North-Holland, 1989.- p.1098-1165.

20. Rosenstein J.G. linear orderings.- New York : Academic Press, 1982.- 487p.

21. Schwars S. Quotient Lattices, index setb and recursive linear orderisigs //Doctor of Phil.Thesis., University o' Chicago. - 1982.

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

22. Фэдоряэв С.Т. Линейные структуры алгебраической сводимости //9-ая Все союз. конф. по мзтем. логике, Ленинград,сен?.1983 г.: Тез.докл.- Ленинград, 1933,- С 164.

23. Федоряев С.Т. О cTpyiiTypax алгебраической сводимости позитивных нумерация //В кн.: Теория алгоритмов и её приложения.-Вычислителше системвил.129. - Новосибирск , 1939. -C.I44-I5I.

24. Федоряев С.Т. Некоторые свойства алгебраической сеодкгос-ти констручтквизаций //Алгебра и логика. - 1990. - Т.29, а 5. -С.597-612.

25. Федоряев С.Т. О счетности ширины структур алгебраической сводимости для моделей некоторых классов //10-ая Всесоюз. конф. по матем. логике, Алма-Ата, нояб. 1990 г.: Тез.докл.- Алма-Ата, 1990.- C.Iw5. .

26. 1'edoryaev S.T. Some properties oi algebraic reducibility . 0t constructivizations //Third Logical Biennial Kleeno'90, Bulgaria, o'une 199°-- Sofia, 1990.- p.24-25.

27. Федоряев' O.T. Конструктивизируемые модели с линейной структурой алгебраической сводимости /А1ат.заметки - 1990.- Т.48, й 6.- С 106-III.

28. Федоряев с.т. йзэавксгаще алгоритмические "эссоьые прсб-•тт. Проблема спектра и состнозений а^ритшческсгас размерностей. -• Шгчскбзгрож, IS41с. - (ПрещжнтЛШ СССГ Ояб. отд-нио. Ин-r ыяаеммаги ; & Ж).

•

Подасаяэ к печати 03.04.91

Форм;*? бумаги 60x84 1/16 ООъйм 1,75 п.л. 1,5* уч.-гад.л. Тираж 100 жз. Заказ 59 -

Отпеч&тю на ротапринте Института математик: СО АН ССС; €30090, Новосибирск, -ЭО