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

РОССИЙСКАЯ ЛКЛДйШ НАУК ClIiïIPCKOti ОТД1ЖЫЙ Ш1СТ1П7Т ШТйШШ!

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

lin права* p"K«ii;ioií

Bti'ínXiUt Николай йчоильоЕлгч'

'/¡¡¡i 517.11

ГМ'ЬКЛЖЬ! С 0РАКУЛЖ1 И РКСУРСПШЫХ НЕРАРХЛЛ

0I.ÜI.G3 - иятомат"чоскчя логика, алгобра и тоорая 'мсел

к п т о р о ф о р а т

диссортпцил un соисчакио ученой стопенн П'л'.туря фиэико-ыатомотичоских наук

Моиисяблрск - rjj.

Работа выполнена в Институте мятоматики СО РАЛ

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

Л.М.Еэрздмнь,

доктор физико-иатеиатичоских наук А.Н.Дегтов,

доктор физш<у-математически* наук А.С.Морозов,

В<э„/даи организация - Казанский государственный унпвореитат

ни. D.И.Ульянова-Ленина.

заседании спа^алнзиро ад нлого совота Д 002,23.01 прл Институт».» штг/атика Сибирского отдалении РАН по адросу: 630090, Пошси-С'ирг.к, 30, Университетский прослоит, 4.

О диссортацлэИ ьюглю ознакомиться в библиотека Института ¿лэдошиш: СО РАН.

Автореферат разослан " ¿ " ('S-u; --1У32 г.

Учений сикротарь

СЛЙЦ'ЛЭЛХ' GrïpQBTiîffi&I'O .

corara Д LG¿.H3.0I

Заща ц состоится

часов на

Ь.Г.СкосирскшЧ

ОСУ 'а

ощ'л хлрлктерист;ка ти

Тэоряя ¿»тело,-ни! с срэку-имп составляет чаотз об^ей тзо-рг.й .'•6cTp3K7Hc.it внчгслшоста, изнзччяыго шмащой з себя изучение обсбеанно-выч.юллмчх числовых фулдцяй. 'Гахий ф/шаглл могут задаваться посредством программ, содергсацкх в качество ало-ггэнтзринх шагов т^вят/.тт дз'Лстяяя, йорг/ллизуомуо в бядо актов обработал к "орзкулу": маицка задает оракулу вопрос я, получив о'геэ? (если получит), продолжают вычисления, прячем этот дпэлог маикнн и оракула кударуотся чяслзмя. Обычно задаваема г.опросн нздоляшся опроделйшгг:м сшслом: а ароотз^кои елу~ чзэ это могу? йпчь вопроси о а: тчепиях кзг.ой-ллбо нврскурояшюЯ Фуякцтг; болеэ яятеросная с-гуация - когда задастся подрос об ок.оичтсм кзкого-лябо ви--{Яс.тат9льного процесса, производимого с зтчм до орзкулом. Б последнем случае шобходлш, чтоби оракул бил частичкой фу;ГКД!ЮП, яклча возникло бы противоречие.

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

Т.. В ато" тпорм пзучаитол конструктивнее обг^сты (числа ц протратят), что лз^аиляет ь/ трудностей, связшгяюг с рассмотроимо« збстрз/ляхс сбьохтоз нозавясвмо от возмокйостя .x кьдйвй-дуального окисаияя; прл это?-, впрочем, члслтмогут выступать кчк код и абстрак-пшх объектов (функционалов, н'чжеств, ордена-чоо), зичяслякчх с ерзкулсм. Хотя рассматрпвззшз в данной тя-оряи "алгоритмы" фязм'юсхи :троализуеми, емоэтся еозкояность :ч;Ы)р;:ть о "Бос.браггавчих" зычясленаях.

2. Сз'л оракул яб являзч я коне тру к'гявнни объектов, но о:: скорее пр-хчеткляэг собой вообще по обдо**? (дсяустакоо зкачонио

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

3. Т-'яссуждеойя а этой теория, <5мьшоЙ частью, эффективны в следующем смысла: юи доказательства теорем существования (гада . .. ) требуется, как правило, указание обоб-

щенной программа построения у ко X . ТакоЗ стиль доказа -гвльзтиа мето/л/ютпчоскп Sosee удоьявтваргтолэя, нежедя тео-ротасо-гаотасгаекнио раесугдвькя о "чистом" существований.

Инторос к оракулъной вычислимости, в значительной мере, стимуларувтся яссдедо.чаншал в теория иерархий. Понятие мзрар-хий возникло в мьты/атпке независимо от теории вычислений: если гмеются кехоториз проотвйиио объекты (открытие множества в континууме 1Ш~разрешимо множества натуральных чисол), а также набор э^ужтавлых средств кострсзния более сложных объектов, то возгшкз'-т вопрос об, язучьнял класса тех объектов, которые ■ихко получить на простэйлшх при помощи выбранних средств, о классгЛ^когш» .ix но слдаюст;: п т.н. Таким образом получается то, что естественно назвать иерархией. Можно исследовать совокупность таких сбъектов в не/.о«, - например, выяснить, хватят ли во ох бсрелввск»'" множеств для построения какой-ил-оудь иитервокой части математического анализа. Тут г о з не на к г метздологпчосяяо проблемы, которые можно отнести к "обоснованию" ¡.«ат-зм^такя: вцбранниь сродства конструировании избавлять о? 'Ьошттрльшх" объекте!?, и промоделированную часть математк-кп можно считать, з некотором смысле, обоснованной. Но ыоано изучзть са.^у иерархию тик систему; ото ¡ложно условно назвать "оспоейниямл" математики (х^слодоьаипом того, как оно устроена. кзic могут быть промоделированы ра&ккчнао математические сущности). Здесь нас будет интересовать пиокно этот последний аспект.

Сначала иерархии изучались с помопьк средств теоретпко-кножептввнного конструирования (дескрдншвнзя теогпп нводоств), и впоследствии таксе с использованием аппарата обдай рекурсии (регурсивнне иерархии). В частности, вшрокое применение получила метарекурспя, обобщавшая обычну» aoop.:i> рекурсивных функций ::а ординальные функцял. /!дя общего* свасапкя класса пс-роадлегах объектов используется такзо теория рекурспв'ьчх функционалов. Автор диссертации, по-влдимому,. ыгор^нв оястештк -

чески применил теорию оракулов дал поог'ршшг и исйло.а/папяа рекурсивных иерархий.

В теор.ад алгоритмов, со. еру иен во зарозд'лшя, расемагра-валпсь вычисления со ьсюду спрэлолвкшки оракудими (относг тельная рэкурсявнооть). Теория шпяслепий с таклш сршгулами иало че\ отличается от оби-лой теорнк олгоритчон. Икмрко здесь првдотаачяег сравнение оракулов по лх силе; в этой снял», бала разработана теория степенен наразрэшшосгя, которую екерво следует относи: к традиционной теория рекурсивных фун-щий, чв~ явли к обобщенной вычислимости. Напротив,, при псаомьзоъаиал частичных оракулов сходство с теорией алгоритмов кончается на уровне теорем об универсальной фуню щи л о нбподвхиккой гота.

Понятно' частичного оракула возникло з тварал чыписдимнх функционалов конечных типов - в связи о ойобцониоч эдак ри» курелвяоетя на эта достаг жм вйотрахтннв объекты. Порыхмч-з--лыю ярсдстаалбкпе об оракула присутствовало в этой теория лить неявно, как неформальный комментарий к дошл ь то громоздкому формальному определенна. Прямеивтельно к функционала« типа. 2, такую ш^делимость мохно определить из языка оракулов совсем просто: вычислимость относяталь" о «Зуккцил л функ-

ционала 6 определяется как кгаслимость с оракулом ^ с • представлямцим собой ыяншальную частичную фушецчи, та куя, что-

сЖ/, б ^^ - (£) , п если улшиа с кодом 2 вычисляет а оракулом с71с1) с тотальную фушецяю р , то^У/, ^ *}=(]($) ,

Особый интерес пмоет случай й - Е , рдо '/Г - -чи-^/ -

гор» ( £ , если ^(/З^ и Е(]?-'/= / £

но« случае). Такая вичлслимость связана с иктуятявной идеей бесконечного перебора (бесяояечно-бпотрого вачяслеяия): когаа к оракулу ^^ % яоетунавт вопрос о внчясдамой с нам цяя {> , он как бы мгноьонно нэробггрзвт ¡зав -ю з.-аплчпя л выясняет, есть -та среди нпх нуль. Оракул 31,)., I г.ассос'ок выполнять как прсетвйдьй вид ¿еохоивчкого (при сх^а-ео

на вопрос £ ~ , где насльа Я уяу не ы.:ааг иоиро-

соь), та к я "1люгокрз'пша"_1£2рв1'ор £ о <&•...•>?, г с»««-»

очередь, яопросы вяда * ); тага;.; образом, ии.: прянут, сиусо-сЕсн ятэраровать д^аглн-оиератэр по ¿оторио о

!ш1 в!>ч/.сл.*<! ¡^ .

и

Теория вычислений с часмчнгаш оракулами имеет особенности, обусловленные возмоиностью неполучения ответа. Если шатана задает оракулу вопрос, не входящий в ого область опроделения, то ес; дзлыгайыое поведений ж определено (машина "застревает"), Таким образом, для машны Z. , работаэдай с частичным оракулом ¿F , имеются три возиолностг: Z оптанаачивается, рабо-■ тоет бесконечно, 'Z застревает. Для всюду определенного оракула цоследиего случая быть не может. С появлением трот:.,эй возможности связано то, что, в отличие от обычной теория алгоритмов, проблема остановки для мэшн с частичным оракулом мояет ■'оказаться "полуразрвазиюй", т.е. орак: : иохот оказаться спо-собпьм решить следущую задачу: пусть известно, что машина % '.вд застревает; требуется вьяскить, остановится она или будет , ! работать бесконечно. Для таких оракулов естественное определэ-1 те nop.iíncbiMocTK соападзот * разрешадасты). Поэтому под $ -, пзрочмеяимямшю.адством в теории вычислений с оракулаын пони. мается., область определения ¿f-вычислимой Дикция. Некоторые ',мнояо;тва, хдактерхзущиа оракул cf , как то: множество'Т(Э} кодов cF-вычиелгшх ординалов и множество кодов иа-

'¡1ый, rf-Еичкслювдих тотальные функции, - могут оказаться с/-¡герочислЕШгля. Одкаг:о яри '¿акои определении ¿/-¡гер-зчхелк-мости для класса перечислим!« с оракулом сУ множеств но удается, вообще говоря, доказать его замкнутость относительно . объедшэиая и проотяровакяя, а -функция'с ¿} -перечислишь гра-. фшеом на., обязана быть ¿f-huw/л Тем'но менее, существуют

частичные отзакулн, дта которых класс перечнолимых множеств вое so облагает келаамшйовойотазмаТаковым является любой '"ре-гулярдуЗ";оракул, т.е. оракул ^ , с который по кода кепусто-1*0 с9■-iwps-íFcjMMoro миояеетва мокло блчйслят^ некоторый его элемент. Из-чркыор, оракул JÍ,/., £ регулярен; кроме того, он , "слабо фуидарут.е. и и) суть

. Д/ £ -Збрэчясаямыа мнохогтгя, Оояощой хйтерес представляю? »■менпо рвгдоцшя к елабо фукдйрэвашшв. оракулы. поскольку нт:>ямзияташ>но к н»ш sexurais програжлрования при збрегаат ооо-ÚMUiJf) гибкость. . '

Творя» оракулов цргдетавплзт антороо. {а-л.-льк ирсчого) как . •J'Ojííi иридстзаяолця маамчлдчовпдх зкзнйЙ. Дело р, топ, Чло т.итим кэтфятк&С в рашаз: йаиторо^скоЬ ttopr.-A яюхьоте

(верило, в одаой иг оо ¡жсиокэткческих исрспй) страдао? скрч-там недостатком. Прчздш транейкяитной ^¡дугами (в той чда.по, р.а тасаситве (л) кошчяях ординалов) используется в этой теории применительно к .тебому свойству, выразимому з ее языке. Однако, как аеиестно, отот принцип не срабатииает яри.лояятолт>-но к "лечетк:.*и" почятням; и поскольку з кэнторочоко.1 матошти-ке этот пряициь утзерлгдастся без ограничения, тс ач л самим все расскатряиввг/лв з ней понятия и объект»: ыалчг-ллю сгитлятся "абсолютно чэткяш". С другой сторочи, осла гл<| рассмотрим фикцию, "заданную'' посродотэози выбора, т"> оо чред ли допустимо -грактоезть как едьозпзчио очродзлнчшй обмзкт (хотя би я мыелвлкни), чго из согласуемся с яухсм канторе во:сой теории кнокоств. При болеа тщательном исследовании основ математики ~,кзлогич;ше обстоятельства выявляются в ояязц с оисиомоД стопами и даже о яспользованисм (|уккцлояалыдах квпнтороп. Ь общем, кадтороэекэя математика иоотулярует для своих объектов такую четкость, какую она сама но может обеспечить. Поэтому приобретают кнторос поуски других средств организации г.?ате;'.а~ ткчоскогс яшюиия, в основу которых естественно полоккгь ие-формалшус идею тоорегико-шюкз- твешюй э^ктввностя. Иекото-рцй род такой эффективности, более тл мзизо нсходявдШ из экспертных оценок (отказ от аксиом вкборз, ограниченно трансфя -китной индукция счетнпг.я ординала:.;.?) бьл взят на вооруженно дескриптивной теорией множеств - в шдз- эвристической концепции "называемого" множества, виступащей в роли методологического ориентира.

Следуяаий естественный шг состоит в том, чтоби форлелизо-вать э^фктквккз тб^ретикач-'.ожествзнныо конструкция 3 ВИД" подходящего язика обобщенного программирования, что а лрквэдит нас к вычислениям с оракулам. Такой способ 'тх)рг.элизацта математик.! оказывается блике к ео неформальному излоисшвз, нелголи, например, аксиоматизация анализа а рамках расширенного исчио -лония предикатов, которая обычно применяется для ыэтатеорети -чееккх исследований, а не для фактического доказательстве теорем. Напомним, что пра де^ор?.: пыюп изложении математики :,;ц постоянно сталкиваемся с алгоритмоподобяшя процедура:.".;' (вроде последовательного деления отр<. уса' пополам ,в поиекзх продальной гочкк), так что глгель об использования обобщенной вычислимости чаиряииБаотся сама собой..Использовать орякуля для фор^злгзг -"

шш математики можно по pa3K0f.ii'. Можно имитировать конструк -тивный анализ, с заменой рекурсивноети на ^-вычислимость; другой способ состоит в том, что с оракулом 'У соотносится некоторая класс абстрактны: (наслодствеано-счотнмх) /лшкэств, кодщэуеш« 3- -вычислимыми деревьями с обрывом цепей. При. таком "квазиглгор>глж1чвскоы" подходе естественно ожидать,, что ■так называешь нора крошимые проблемы, касавшиеся вещественных часал и т.н., могут получить однозначное решение и что их неразрешимость есть слндстбиэ неадекватной формализации, а отнюдь не относится к свойствам физической непрерывности. Проблемные .исследования, в определенно" степени, подтверждают вте предположение.

В принципе, теория оракулов с ее установкой на "бесконечна«)" вычисления, способна слунить ориентиром для выделения ин-тересгых классов конечно-переборных алгоритмических процедур, в роз;'ЛЬтато чего актуальная бесконечность могла бы оказаться веэгг.- лить. удобной технической фикцией, которая спзэза закла-дааэзтея в гамыс-ел интересуете Ё нас программы, а затем устраняем я. Пре^етэвдяат гакад интерес выяснение связей мевду ора-■'•ульяой вычислимость» и другими аспектами оснований математики (ноггл лдартхше мздехи арифметики, трансфинитныо иерархии фор-мпдъднх систем, аксиома детерминированности). Предварительные попытки такого рода производят довольно ;бнадежнващее впечатление, Однако при написании диссертации автор но ставил столь отдаленных ц-злой. Ее содержат1-} примыкает к традиционным ис-сдедодагада на темы абстрактной вычислимости и рекурсивных иерархий, 1зтор стремалс« создай, целостную концощдаю лашишю-орагсульнр" ьнчио.'пшост'п, обособив оо от сшчиого' материала. Ведущую роСи пои этой играло порегицешш шпита с "о|с'лктив-.иых" (в абстрактном сшсдв) объекте» на квай«»ччисли«и<з процедура. Такая у ¡-чютэ мотивировалась квдганчем л^гулли-, по ио-у;-.окасстк, он-.'ишльннй уровень .'воротеко-ч11-.041стшшоК (т.о. но компьютерной, а скорее "человеческой") ь^Кьстивноотл, «й /.о-актуальная бесконечность ате сохранил.1) '!ь ипку» "оошае-гость". 1\:ерон нетривиальное™ та-.-.ой кснцс.нцйя о. уклт исследуь-«я "л д«совртааля воЕмоаносгь кодедирован>]ч лч^ (жтяк сд>с.гл<н-'",'с.дч ^'•ху^аснок (.изтоматикц.

История и вэатлссвязи

Хорошо известно, что разли'-пше укоре.ывшиеся в матомэтш«» формальные определения вычислимое та оквивалентг-, и это сохраняется при релятивизации к тотальным оракулам. Может быть, по столь общеизвестно, '■'то при перэходе к частичным оракулам дан-лая эквивалентность, вообще говоря, перзстаот иметь аосто. Например, тьюрикгеза зычясл/мость с оракулом с/ равносильна эр-брэк-гёдолевской рэкурсизности относительно только при условии, что - регулярный оракул. Ограничони? тотальными оракулами (при традиционном изложении теории алгор: :дов) мотивировалось отчасти направленностью исследовательского интереса на изучение степеней неразрешисовт;:, отчасти ко, из до полагать, было связано с отмеченными выше особенностями программистской ситуации, возникающей яри рабого с частичными оракулами, каковая (на фоне обычной теории вычислимости) воспринималась» зго-видимому, как аномалия.

3 то ze время, теория частичных оракулов позволяет глубже опутигь приншгшгальнуп разницу можду тотэлышми и частичным вычислимыми ф/нкцияьм. "же при построени,: обычной теори" алгоритмов частично рекурсивные функции играли роль идеальных объектов, образующих СЕоего рода ''оболочку" для совокупности "настоящих" алгоритмов, - т.е. они были вводена ке столько рздч них самих, сколько для тоге, чтобы сдолать болев "комфортабельной" технику прозряияировзнкя. Естественно возникает мысль о глрьяролаиик этой оболочки (¡той '"охранении саиаса тотальных ычиелямих функции). оту кдев мотао роализовот^ на уровне вы-чнелимоотп с чпотпчнми! оракулами. Например), сопостаззлозгла пз-лестной тоорег.ы Сакса |,42.] с речультатом § 5 главы 2 да.т ift длдсортзц.14 ио'яг'иаэет, что мездш построить два оракула 0/ и гА . раяроичщич одни л то ко числовые множества, - оболочки т:от.»^ы-< к<""Л-лч>ко "чудородны", что по каасше, ¿, -разреаззещей »•>;«> то .»о гр'г.^о-зтво, нользя аТ<|« ктавно построить машину, -раг-р.П:.а n,iyij у, •f,n iiiiov:>;iv:r>o.f При этом обе оболочки поззюллтель-¿■о с Г'''-Jn. аатаоцс-шзшли", и предпочтен И'; адкг'!;

•и ein '¡до гпота.ч ло^.л.^доззт^лт-.сгс':.; коитокстоп.

('•,;}!•'• С UH 2 с:.п/.'',тйя :"л'(п.сл.1' :ооти относи только тотального 'С-"."'-'-! i-u mv.ti.. - ч шо".естза Ij ) носят р'_гл!н>-

ыгфний характер: от конкретного.»¡бора В больно зависит объ-си клагса 3 -рвкурслвних функций, нежели его структура. Все. у.о пря сооткасонии Ь -рйкуролвности с обнчаой рэкурсивностыо обнах)угав.ч:дася кое-хакиэ об!""о>ггельстаз, где особенности, присущие выбранному , могут сыграть роль и е структурном от-нокоишь Напршвр, если 3 очень "плохоэ", то мпохшство и); д -рек^рсавных ординалов совпадает с множеством рэкурск-

■ вных ординалов; если хэ потребовать, чтобы степень неразрепп-

' мости В) (будучи сколь угодно большой) "хорошо располагалась" относительно ыножостза кодов рекурсивных ординалов, Зтот хорошо кзвэстлай факт (теорема Споктора) имеет небезнкто-

■ распов следствие. Рассмотрим в качества "суррогата" 3 -рэкур-

, они ограниченно ракурсазних функций множеством В (этот прием

• использовался в [40] для построения рекурсивных аналогов несчетных ординалов). Истестаащспж в данной ситуации аналогам снчасл/мых: ординалов яашио*. ракурсивкнэ деревья с сбрыгхж г) -цглей [1] если ¡} I-сводимо к множеству их кодов,то

; такие ордивзлн совпадав* с *) -рэйзрсишшя ординалами. Напра-

■ шва.л'ся попытка распространить з?ат подход ш 5-'-вычисли -у>С"2} с частичным Ц , Если В„, '"адаптировано" (в подходящем олг зло 113] } к оракул;/ ¿)- , то представляют опродолен-нцД интерес- тотальные на Б фикции вида ^ с ¿р-вн -чаодтсли . ^ . Отыскание нолходадой о<5г зчки для этих фуш; -дяё, вэоб«« говоря, нетривиально 'л позволяет уловить значжлув информация в связи с аксяомэтизацкой (в стиле [39] ) теории а б; тра к?но й вычислимо ста.

Продидг,цг;о (сравнительно частдаа) гздочания исходили из нрздетааленяя, будто теория оракулов и впрямь сыросда из внутренние потребтотеЗ теории алгоритмов. Однэкс гдэйный источник оЗобц&шхой ¿ычаслимости скорее сле;£уат кеглть в доскринтивыо!": юорни шюжест1; и в том "кризисе" санов из темп тики, на фоне которого она .гфйникда. Идея 1!построло;лого" объекта

укз тогда вад£ину;:ась на дор?л,'й п.:хп п лишь всослодотгаш об» локлаоъ (с пользой для себя) э алгорач^чоскиа ''одезды11. Нв-прииор; вакшй класс гвпарерг^зтичвекях числовлк м>:окэст-а .ц-чрвоиачзлшо озродаяои со шз&гояш с баролевзюи.ш ;

■ о°::-дип р кочт1!нуу_:о, и одько поаоа било бияснопо, что он оо-гтж)' ';) точаоехз.: ¿п ¡¿'ох'.сы, р5г.;,ргн1:аы.г отяосктсгььс &

Соответственно, била установлена связь моь,{ опоращьй "рошзта" и глпэрдлашом. Вежяойшие процедуры..плрпз] ::г.ое:л;;о я дескриптивной теории мнокеств за иэф.1октквныои (зплсть до актов "полос -родственного распознавания" несчетности борелеволпх множеств) били позднее (j.'¿3] ) аярослрованн в маиикно-орзкулток контексте, и тем бнлг, подтоерздеяа их приемлемость, исходя из более .■.юстких требований. Бкрочс.-л» установка из з^фуктавло гь была осуществлена в дескрнягяьлой теории г/лодсств но совсем последовательно Сяз что указывал II.II.Лузин [24] .): охталлчонпя накладывались на подмножества континуума, а сам континуум оставлялся в псприкоеяовеллостн; это шелушило источником яеразро -«ымых гипотез. Значимость этого замечания подтвердилась отчасти при вовлечении иксисмы конструктивности в дескриптивную теорию }.а?о,т.сстз (работе П.С.Новикова), отчасти аз - я ходе разработки оракулвкого зарплата конструктивного анализа [ 22].

Среди сооромок/шх дисциплин, относящихся к обус-.'й теора; рекурсии, наиболее близкой по духу к дескриптивной теории miо-:.t3cru является теория вычислимых функционалов, разработанная ¡■¿линя, Мссковакисо?л и мпогими другими авторами (см., на призер, [36, 33J ). Ее ося'глоо дости;.;он"о - это все-таки не c:-j..:o по с бе обобщило рекурсашоста на объекты высоких типов, а ссзда-изэ удобно/о аппарата построения и исследовалкя разнообразных хорзрхяй числовых множеств и фушощоиалоз типа 2 (подмножеств ксктлчуума). Зта теория оказалась "генератором" новях средств г<м|л::г;тяогэ конструирования, которые на были "уловлеян" даск-ргаткшюй теорией шоздета. Действительно, керг,-.сд от Д -мио-.хептв сразу к проектиЕНЧм множествам представляется нсоприз -дз.чно розк;::.-:; поз пол .'ольно с '/наняться, что проект»зная иерархия (и ирсяс.^-шлсчч ее гнгозракзляткческ.гя иерархия f_3( ) достаточно адекватна ннтугтткго пеияшзмой теор^тпко-мпоглествоь-ИОЙ п¿^активности, ибо такие рассмотрения соседствует с заведомо «¡оки,)роктяоа.кдсой "перебора" континуума. ые;-.<ду тек, теория вычислимых .т.уккцяоиалов доставляет яа:д очень привлекательное яЗДедткдноо сродсгйо: ток аэзншемкй сулерддзмп -ш тина 3, опр.эделло:.:!ь в тер: чзу оеобценпой ывп'сл^остп, Прлвлз, к к этой теория traaio предъявить кое-кзк::е протекзг..: свойственная ой чрезмерная ирг ягзяность к классическим пз;>-воистокаа (строиштэ к максимальному сходству с теорией тлтг), по«злу», несколько сдергивает ее зоз:-локлостя. Работа с ^ункцяэ-

нзл&мп - это удачныЗ прецедент введения в теории ал гори таз а бесконечно-переборных процедур, но последние более значимы, чем сзьм функционалы. Определенного "раскрепощения" мокно достичь за счет раз.<шчных вар ,ац:тй исходного определения клиниев-окой вычислимости, прямо нацеленных на построение объективных иерархий. числу таких зариаций следует отнести рассмотренные» в диссертации призмы конструирования (технику "накопителей", итерированную ютлниевекую вычислимость, пульсирующие иерархии) - гораздо более сильные, чем супердаамп, но все еще не вторгающиеся в сомнительны а интуиции насчот "наотоявдго" континуума. ' В »тоЯ связи целесообразно обсуить здрсь одно обстоятельств, могущее представлять интерес для философии математики. В .оракульном языке, в терминах вычислимости относительно подхо -дя'дего функционала тина 3, мо::шо полностью промоделировать -класс).ческую аркфлотику третьего порядка (включая такие "сом-ьяте/. лшо" вецн, как существование cynpei.iy.va ограниченного мно»' стел в континууме). Иостроонис етого функционала более или монее вписывается в идеологию дескриптивной теории множеств и может быть интуитивно признано эффективным. Однако при ото'л выявляется мзтодоло 1 '¡¡ческая двусмысленность аксиомы степени, Сама зта аксиома но участвует в данном построения, ко при доказзтельстье существования яужкого оракула используется ухворздеиие, не входж^е в арсенал тео^тино-мноуеотзашшх ерздетв, традиционно признаваемых эффектившдми. Имеется в виду известная леша Хартогса (модифицированная применительно к отсутствию яксиомы степени): монотонная транефккитная последовательность, состояцая из ыноаоств объектов фиксированного типа, должа стабилизироваться (аксиома ..Я- ). Нто утверждение находится в одасной' близости к аксиоме степени, отнюдь не производящей впечатления какой-либо "эффектхайозтл"; более того, последняя акеш -о становится выводимой, если принять также аксиому конструктивности. С другок стороны, весьма правдоподобно, что процесс 'свободного становления" ординалов долаен пирон -даться, если регламентировать его сопутствующая процессом но-роадеиия объектов из заранее ограниченного "пространства", лгрищу!Х роль "обозначений" дая ординалов. К ту]<у жо "постфактум", ко'завершении всей конструкции выясняется, что нукцая .стабилизация.происходит на счетном ординала (что доказывается

в 1- F ). Отпоспться к ОТО..Г/ vmпо-р^лигму, п г .внснглстл. от ствяэки нашего "¿хкфорчызг.а",. Уожно ус'«угреть здесь коков "оарэдданпо™ ai:c:io:.-¿í с^огтзки, но клгоресл:^ признать "пкутренаж конфликтность* •еазлэй. здея э^еет-ишоста, ж алинаиугася во сзалипой гоапрсглтацуя ражЕгвюх ее Ерся&т'лш: (ахссиоки О i и' аксиомы кснгтрултяадсстг).

Так э.и пяатэ, атагяяза J(- «иьгзъиэаотся s ряду "нредодт, -пых" прнчдшюз 5еорда :^-:таестг. -¿тале* как аксиома выбора, аксиома детермилиросантостд, оудастзоваызте ¿олытгх кардиналов, кситинуум-гчпотога), н&:содядося "ресурсных гроккц" ра-

зутого ношпгатшя. Это не означает, чяс перечислен. ;е принципы проото невразумительны: гакднй из к,тс ® отдельноетл носат в сабо (неявно) интаросиую и дгачи. в кг.коы-то смысла, конструкт^з-1'"ю идою; но- они плохо поддаются едслообрзхюму осм:слг.н-г;у s демонстрируют судесгвеняук рассогласоъзныость нм.их интуиции по поведу концвшшН множества к бесконечности. Згряйчталшлл пршэром яаляотся принципиальная нооцредоенноеуь в вопросе о мощности континуума, заставлялся усомнч-гься в дризичногд лред-стаая&нии о непрерывной прстя;.:о::лостк как о зноллс оирлдояся -ном точечном множестве Другой пагаый для пас пркмор - "катс-логлческиа" следствия аксиомы вниора, в которых эта аг.олома по-сущестйу иепоеппиа: те so реь^льтатн (х'арздокса яькьго cbo~cvü3 неизмеримых мко.г.еотв) легко получаются в конструктив:; о.и анадл-ге (и в evo оракулько!' версии), где кот надобности поотуллро -вать принцип выбора в качество самостоятельной, аксиомы. Самым естественны:'.; дочем для размыпдгд :tí на эти темы яшются альтернативная теория мь'ожестз (ом. ¡_I7] ) с присуща ой радикальной ревизией бесконечнс-тц: таковую правильнее воспринимать ко кок поотквополомюсть конечного, а как ого аспект (или как wtr о-образио таких аспектов). Подобные рассмотрения выходят зэ рамки диссертации; однако момго подойти к той яы проблематике, исходя as ^Ф^ктивкстскои установки. Теория оракула дает %дя i;того ноххолщво доруэльисэ оснащение. Поясним вкратце, что имеется в виду.

Вште отмечалось (п ерчза с оракудъним моделлгриклл"-"'-:' анализа), что :.ног>о«?ъазалз "корйзрзига.оста", Ёозшьахдао в то-оротико-млс^естзонлой математике, представляют собой издержи» формализации - чисто логические ур/окты, £•:•

uudopou аксг/ом, отчасти л;о аксиоматическим методом вообще. Прк-мзнитолыю к идо®: члсла, шокаства, иопроривлостп всякая ак-шол7«;:зицкя - ото всого лишь лэрматЕвин!1. акт: речь идет (в редощеЛ стошик/ об cp;iei[m".iii'.u а нашкх собственных мыслях, .с бьяо бк иихвпо кокать тут "сашо правильные" аксио»н. Но в такой случае, например, аксиалу выбора и аксиому двтзр:»шнирован-ис.сси'рэзул'лае раасматрияать па как свойства разных ".»яров" (;з.'.ч: tu:« ¡голу нооонлзотиж), а как разное тондшщки, сосущост -ву»жо в одаоя "дг.'.ро". Этот записал удобно реализовать в ора -кулллой штамаише. Збобц-эшю-констпукгашшя модель классического одш.па, построенная в гл. I длссортацил, позволяет трак-хормть кокструл-гивт:й анализ (в оракульном пополнен/«) как надстройку ¡гад 5У1аооичаскии (а нз как ого "усеченно"): по-суцост-ву здазь оОвгрикэотся (в слегка гоодиоинои виде) разишь мокду точеч/иш к ианалптичеокш.Г оярэделонпеи вещественной функции [33] . Соо'л'веч'ствон.'Ю, ш „дкучаем возможность формально раз-лпча' ь ";юото.'я;;..ю" множества в континууме от "ненастоящих" (су— цес-"ду.№;х л!Ш1ъ в надстройке). В частности, язвзстши способы яое гхмаап иопзкеридох шокзстб г^окотруктазазируотсд в торил -пах энчйолоплИ с нодразудювао«-».! оракулом и задает о'оп мнояо-стьл уонио как "яоиастоядао". Том самим возншеаоз довольно соашся'Солыяя теорля аоезмор^ш люжаств (могутая представ-.c.'tvi- литера« в сег,зя с осковарг.'.яш тес; ч взроя-игастей); в то ърош ко ticwnow.>iK!, что задействовав иодходедип образом аксиому дезалности « сово^ниеяствуя ваш оракул, мокло дабйтьоа, wiu все "настоящие" ?дю:,сосхвэ <>ыля изиеркш. Это Е било б и шземкм оооукостзозшмем протаводслохных тездашшй в редисах *opou.o jctoouhoü теории.

Тоорйк RV4UfAiöiniü с оракула;"";! таено снгкаетоя с мстарзкур-оло;;, o6o<k,i»!i8S испятае рокурснилостк иа оА.«диьалышо функцка ¿г порэгдчзд&£ рохургкзкнв аналоги болымх кардиналов. Если оракул J~ рн,;и:'рг;н ü слабо Qyv. -чрован, то зге виоота 10/ (длина огрела ,'f -аячг.слямых ордагалов) является допуст':".и.! (чоп-сърукелгт^гуля&ш) ордхяалоп. Поэтому | ' --рсгкурои; ыодв-л';;руоюл в терминах ^-вычисли.;сотл. Особый ¿-¡перс,« прчдстз--.-itvi- случай, когда оак орзяул $ являются ]'.. /ну-япс-гсй'«^ v'jkw "М. .Зиплсляыюзть с. закачзг орокрккй» црздгпьдл.и собей

«wxs23l«vü обсбвдкзз ^уморацкомйогз*' пол"одо i; h3y3|*.»!:jp«>i':t , . ' ■ j.4

описанного в i. 3? J . Мегарокурссл цолучлла ntpoto.' примами.*» прк исследовании рекурсикяпс иерархий (cu., юиродср, lü-I, 35, 41 j ), uto обусловлено связью с теорий.! «лиг.аумих (i./:¡.üw<-оизлов; л четкости, конструктивная клдсс^ижлчмигь i\);u«iru¡i равносильна хЛ^кураяшюс'п:; "гпнорл'^мтй" (опорагд:;: ".;>* ¡х-.'»" в декср:гатянной тоорал пнозеста). Осгюшшо 1;окдг.*>; с-: могу т служить удобной характеристикой ttHW.W-.'OJíKiol« «клч оракулов и ЛХ Е-.Й^КТИПНОСТ^. С Другой йУОрО&Ч, ТКОрВЯ орНКу.МИ япляетсл ксгсчж-чш более «осткой (« ¡ш'уитявпо более дргип'чо--¿xjü) конизгшк а'аоретлко-ьаюлоотиешюго рф^ект/ьн?.: ia (см.главу 3 досозрт&гда-л), ¡i потому она згитужтод? обособления и самисг-тоятэлы.уа логпко-мзтоматкчаакую дчсшцлину.

' оши? ДЖСЕРТЛЦЖ '

Диссертация состой' иг вводокия (зкдвчагцого нредидумео обсуждение) и трех глав к содоряот 152 стр. Первая гла'еа по -севдр'ш сб^-зй теоули оракулов с некоторыми выходами в клнйиод-скую вычислимость относитяльно функционалов типа ?. '3. В пор-m<r трех naps:ps<¡ax .изломе«игомонтахниэ свойства рогулярлчх к слабо фундированных оракулов, поете.чпо кспользуемые а дальнейшем. В $ 4 предпринята аксиоматизация вичаеллшег'К i гэкида оракулами в язикб элементарной аряфгатшо: с добавленной в сиг-нззуру символом оракула. Покгзано, как колшо в лолучзкмсГ. теории промоделировать "птерарнфмэтическую" вичйслимовть.

Я заключительном параграфе слева ± излагается "техкшп накопители" - эффективный метод построения ззсылд сильных оро~ кулов, порозгдащих обобщонко-колструкгчшичв модели кг. ;с*!вв -кого анализа: арифметики третьей ступени (а такж; более шоо-геих ступеиой). Отчасти об этой уке говорилось "ваш»; ссног-иая трудность, которую приходятся здесь преодолевать, состоит в следующем: оста по рема шлю тира Л пробегают ь •"•«шудв

у- -;:ичисд;1!?;е ууцлшокэлк, то (как. устаковдоио ь ÍZ?J } <,о-ог^п'отьуп^я схема аксисм с^ерттеупия ас kcvjct <<:•:••}> доза/мзде 1 • при 1-зсом о1" . Иоэтсиу Кб до наложить цодуод>в.:' • огрь?лшкйя на G'Siwc-tr. допуекллих зю<т>?ь*Я зптх nepevwanux. О») достнгч с;г р-...1лг,.ч?,13йиц11 ооно^ього ерг.куда ,'Т :<о eksbooi-ou-

•, с; л. гм /"' ( nw:,--:. :?0

числимым). С вокогя.» »йййЙстаа орыдлов -i tÎ>J ьк-

ДАЧЯМТ 1я ¿згнллйояалз«» сзк&змйаьмэ к Биде: G ((}) - iu)^ дая пялусодж» i£ 4ïv аргумент Р репрезентируется

оракулом слз s «ргг-оодпйяйгчЗ'.'! к ><агвдд tu ло случаю вычисления G (?) , Огрчолчежяс skï функцаогалсв -вычислимыми /3 дает яузькую гадэль,

Во вгоро? глаье изучается итерированная кллчкеьечая вычи-слагссть - вэоы/л обсзд схема построения лерархкй посрсдство'л Н')Е('1Ш';.:а:гля орекудоз на ординальную куквазцаяУ.'сЛ il'J"" I

а>у]ъ н . м

£ Си ) ■ Каждый такей оракул ui ^

('Li j^W обладает характерны'.' свойством клтшозеких оракулов: — 7 Г^

~ t (bJ) " а так-:9 разрэааот график л преды -

едщих оракулов Jl^ равномерно по V -номерам iS/i^

есть (мпимаиьная частичная функция с этими свойствами иx<\z

влечет по построение cyt^ <~ t/tj,. " • Мо.кнс реллтиз'тзоьз-ь етп

оракулы к лtjcibiM функционалам типа 2, определив тем самым семей' 11 r L

ств) I Л. Г . 3 у Г досматриваются лросгййьлло свойства этих оракулов, следудг,по /.?. их определения^ в частности, устанавливается, что переход от J/7J к соответствует "гиперциклу",

Б §3 г.тэи 2 изучаются так иззкзаемяе тэчки насыценил, оп-роделя-мие условием: Jj*{ïfl)~ ) (в этих точках

гу /' с "л"1 ,

Бкчяслител£.яая сила Jlv мо:кит существенно возрастать;.

Сеногной результат (утверхцение 2,12): Т есть точка насыщения V тогда z толысо тогда, когда множество Ji [ j]

номеров С < -с не Jlzv "разрешило.

3 f< 3,доказывается "основная теорема" об ятерироханлой ¡шяшэвской вычислимости, играадал ключевую роль в дальнейших paccMOTpa.:fi.:jr. Ока звучит так: пусть оракул ¿f- еллбо пун-ДйрэБак и вычисляет ; к пусть [\>J 'J- -перечислило

и граф;.;;;: т j J"- -paapeiviai раряо/'-ор-и» по ^-но-

мерам С" . Тогда ¿f -вычислим (равномерно по естест-

гС«яоыу списку параметров).

J 2 -I предметам рассмотрения являются "рчпчоморно-рсгуляг-

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

В § 5 вводится ионягло течки <5 -насыдекля -• "^а.'.орац'.:.'1!;-

ною" аналога ка'гдаалов Мало; устанавливается, что .эдот;« ¿тот-"/у"

вуючаи оракул ¿4 и не шмвалентеч кнктсоку клш-гшвски;.-.:/ орл.улу % (утверждение '¿.'¿й), а для прочих точек наонце-ник такое представление возмошо и строится ооотглтотлую'длй функционал & (утверждение 2 27).

В грэтьей главе акцьнт переносится на исследование л^ак--тканых иерархии {Л * | = ^ . Мдегэ дЗДюктибностл мо.-ло уточнить дпояклл способом, В § I эффективное?! определяется, как "равномерная шжорируомость": ^ эффектевна, осли для всякой "рогуляспой" V/ казднй-оракул Л.* вычислим с со-отваге твугацим оракулом /у, "равномерно" (л поводящем синода) по . Уто определение ¡¿окно ролятцвизовать, переходе к иерархиям ¿2. ^ о, ~ { 'Л*'.)&} • " частности, лусть есть результат у -краткой итерации "суяэрджамш" [I4J вдоль ну~ мэряэди V , начиная с В" ; возникает вопрос о сопоставле -яш иерархий и ^ Е* « когда V' эф^окшана относительно а, , а /С - относительно . Отвот яа него (утверждения 3.4 л 3.5) и являются гларнш/. результатом 5 I. Пусть - последовательность точек насыщения V , "степень предельности" которых У . Тогда, если у < (О) > °Р0-

/// « V (г) ..

кV.Л ^ и с эквивалентны; осли же у ,- (0),

то этот результат сохраняется для -г ;> ¿о . Попутно усгаиаа -лкваетоя (утварздешиа 3.3), что если )'<-: ( V - сг- ¡пел.ь пределыюота -г ), то Л^ , эквизацэнтэн юшнкьаскоиу ораку-.47 ¿Н Рс о V] > I1 Г V [ у Л "диаграмма" начального отрезка V длины ¡/ ( г/ -супремум предыдущих точек на~ сыа;окля, степень предельности которых > ^ ),

Другой подход к проблше ©Активности предложи з § 2 главы 3. В основе его лопну идея нороздатодго мгппизма, на вход которого поступает ужо лорокденшй кусок у/4-г искомой пушрацкн , а на рьаодо доляея появиться у -лег.ир % . Ой-щлЯ вид о пи мезинпзмов л<( гзран'торует е^эктгвкосту (в омасле § I) пороадаатлх ими нуиервций; пнт*к'»е4 яредстаячяот покек

"Э'^октизггнх" к.?уэлазю*, д-гшдлх достаточно дтанч'ш нумерации. Ih-î.v п;.п'с!с о счзнвлоаил /зшпям, поскольку у дзетой построить

иерархи.', сдесванпо болио длинные, исколи то, ¡лrrupt.'e c-u.ni лозтро'-кг ран<:о ( I. ЗГ> , 41j). исходя из тоор^тпко-кшзлегтз^&д ¿»•••.•1л-)п:й. UpooT^imn; попчм-ула-и такого рода ял-/t;-jTo i "иэтор.о?.-ViSi процедура", •пон.озаиная из коченной sxcpsno-V' Г ï . Доказатс.ш-.сгго ь^ективнсст!' опто.чсышис nyj.rjpo-цзП (.7Tnnpv,T,'--Fло J.7) - ооноеной por-i:/.'лгат v 2. Б этом m на -рсгрзЖа ррс,?с лгрчгавтзя поргздэший и.изн о бесконечной зке-трапотлцл?;1 ( гуяорз^тэпоюий), трю;:о дс.м'.лй ;>(]<*-жтивные î.71 •.прочий и допуекг'нтдй .пг...-:ь:;о.'*иуопл^п'^о.

В зак'П№Т<з.г.ь:ю:: * 3 гдавн 3 рсс.гдзтгываэт :л ацо один способ построй ¡я корзрхпй, »>ромз\гтсчно>» гзлсдсч'ле ма-жду :i3y-io;ii:vv:.i б главах I S (5$ I, V,) jopc:i.-s.Ei ^(¿активности. Это так казьсаеюга» "яулъзкр^кццо" иерг.рзчи Галцдао мс:шэ г.род'.тзвлят:- оооо процесс "аы-оно^юю" иоротды-пл •,; многозначной) )г:.г,;э;рч1!и;;, гро:.;я от зромзпи ярешваамкй "кзтаклягмзггл", в результата которзх пзротдаеггая пу.-лорац'-ы укора «^ается, но ъи-•1з делазтел болез "толсто?" (за счзт гасягореиия :ииоторнх но-«оршх ¡ihoxoot») . '.'тот (нз вполиз .»лскотоншй) лроцосо когда-то вс«-. ь.р стаблтлз лрустся, дзвад нумерации с иу/зонта свойствами. Б 5 3 таким способов отро.Г'Ся цораргпн J'1 v , тгпезч что совокупно? п-. тза&яьких Л^'-ЕКчаслга/их ijry;:îxyiï образует модель 04.3MH пкездш своршваззя с двумя фунедионзлъикш кванторами я с £у'псцис'4&льшын лдрамутргж. Последлэ€| судоствэнпо : под*,-ль дзул'!'.взиториоГ. схсда бот параметров строится гораздо пг'лц";. ;1о-в::д"1.!о:.:у, o).*pam!4eiii.a на число кванторов лскнс снять, приспособив тзхшгку "пуло>гарова{в.я" для г.^ск'тизиг.г'щ:;! нозгро-

Б зя!'лсчо!Ич этего разделз - сведонкл о публькициях. Материал г на au I полностью изложи в ¡.11.7 ; результат» 4 л 5 ранаопубликован в )'£, 10 J . Нокстор:^- прлшкад-део егда результата автора, но в:ш)ч9ншь в диссертация, коако найти в

Розультзти, волюдгеш во вторую л трет;>в а .<:••, опуб.ап'С— в i l, 5, 7, У, 12, U- J . Сод&разлт pacov ¡_1-а, В/, относящееся к той де текатлке, но включено в дисс^ртациа» во лз~ 6й;;й;ыо ее поротеузкк; отчасти оно блло уг.омянуто ю вводзнл::.

[ 13, I5J

I ъ

Полученные ¿второй результате по теории оракулов л рочур-еивннх ииоарпй неоднократно докладовзлксь на ое.дапре "Ллгг.б-ра и логика" (Новосибирский университет) и ял раздаст ко «•;■>• ренцклх из :,:агсиа/ическс2 лошгя и програ.'сгпгогзлп:«, а ток.» с на Мождуиародоом 'лонгриссе пс лотке. ;>от)ссфи:; и методолог:.;; науки (Иосчва, Í9LÍ7).

В ОКЙСТНССТЯХ даОЖРЩУК

lis пи следок дяде* краткий обзор результатов, полутлшш под руководством автора ого уче;шгзмп. Зтя результат:; органично вписываются в томзтику. диссертации я придает оггред» лсинуя целостность наложенной з не* теории.

В связи о разработке'-; -конструхцдряо^ аналиаа, ВД'а-новнм бил ояродолон [22J нокоторпЗ класс оракулов, впоследствии названных сильно бунд ровзш:к:,:ч. Для нях постулировалось гудаетяоьяние "вычислений", знадогичшх сстЕотстиуотда ocvoci:-таи кз теорьи внчкслаюсг % я&даздагся гшчкелягшмц

деревья?« с обривом «спай. Из определения сильной фгаодэопзп -костя (вспрокз :акой терминологии) отладь но усчатрквялось, что эти оракулы долздш бкть слабо фунди,эваиними. Том m мелев, А.Гамовсй удалось показать, что ето так к что, вследствие этого, сильно §ундировшшвэ оракуля эквивалентна оракула;,; кия-нвевской вччксллмостп относительно функционалов visr.a 2 [19] .

Сялтлз qyíL'.'iipoB.'juKüc оракула ваклы таж,тб в свяаи со еле--лугг.м;я™. же свойствам: для них зуновхвуот van називзаяя скстош "каяанач5скп2- кодов" для ¿f-zivr¿oj¿muz тотальных ¡.¿тещин и ердшгалоа. Благодаря эгеку з $ -коиструктлЕтои ааалигч шнол-няетоя утв?р;1допп8 коктаяуум-ггпотбзн С 22] . Коад том; как показало нзучешю агграрованкой зшшяввекой ипяслляостк, существу ят оракуля, ие я&яяэтдоот сатько фундяровашши, которые тякг.о обгаятя? системой К£:нлк:м;оскиг кедов. Ого ыг'-л-^-ыип вело к понят.'.р ризлетгого срскуя.ч, > в работе

IÍ.IL'Í:;t:!;!;koeo;Í Г20j , .....

сорил стзте:: 2S -23 ПЛлккгороЕоП оягс волр".-^ до1а:ш р.'ч'.тич'.гке медл^л.лглл к.':'.яг н-л'ско:.' i-:,-1-' :о.т.: -

чг^-еленя::; л ос. лг.сем то. чтоб:.: ^облтлеа р^г^лл^лоог".

гс '' .,:,: кз . г.:.у ^'i;..;::,','.- (с г у.;:-

сюра пу^ерацип). Наиболее едтаолрьательной сказалась версия ! 3 ] , ;;отср?.ч попользуется в дачной диссертации для упроще— •«.я йоаоа-орих дслазательств. К итому ло напраппепкп следует отнести работа Л.П.'бедияа Г 31. 32 j , в которых модифицирует-о я опт понятлэ шишиг о акулам: оракул реагирует не только на вопрос, но !/ на гадастдуи еги машину и яотоиу является двуместной '.рунгДг! eií.

Б рэс'кта:;. А.Гпмоьой í 18, 20, 21] исследуется связь ора-гульно:*: вычислимости с метарокуреяе'! (на нроэьтируемых в ш ординалах). -п. рассмотрения явились источником полезных гипотез об абстрактной вычислимости, которые могло принять бэз противоречив, если отказаться ст аксиом» степени. Приором »лого? олугать утпоржденно: все допустгжэ урдикллн проектируемы в Ю , Эта глпотеса пнполнйэтся на $ -зы'пелпмкх объектах, если % н (делен подходяцзт сйоЕстмлет l'¿l] . Соиоставлопио послед.«го [эозу.чьтага о датариало» § 2 л 3 главы 3 диссертации п:лс;'зшз"1 т, чтэ у твердении о цроактируп.'.оотч сэлмсотимо с ".ерюнкми фратментыг.: анал:г.<..

Теорию оракулов r/олшо рззвигать в нвоколыкх направлвнл-нх; p.'ív.s'.', ,j,B3 из шгх. Во-первых, в езязи с мсоладокгтиями но осрс-юл'сяи! ивчсматпки, представляет иптерьс оракулыюз >«.одели-¡•овяг.пс разта'птнх акслинааичоских теорий, v.x £рашонтоь или f?>''g?o Некоторых. способов №»Т-)."£!К'Ч6СК')ГС1 конструирования - о чек: H-.-w.ufKpaTn.-» увошделэсь вше. Вогвторн»', возникает ряд '.•iiyipi'iiíuix пробчэм самой торил uoi«px.til. Особоипо слалуят отпятит; j-nr-r»onc-pnuu;:li еп?кгр вопросов, .кисчк'хся v {доноиля ír<n!;;::.'H>C"bi r.,er.ij ро^длчлу.'.д en да ми ;í¡:íoo:'¡:. Ярзтда

u'j i г; -.'IT) ct.íoch ;ся к s.;v;au.¡ енттомдт:: '.:^"; .и ,i../'!on;v¡ пудь'.::-

• ■ /гГ: .! • ; '"•^jajil.

Ч

рашты автора но тага дкш'тацйл

1. Белжш! '1.В. Зариа^т ".онструка'лвнизс ордщидол Рли'ерл //Алгебра и логика. - 1963. - Т.8, 1' 2. - ЗЛо^-171.

2.'Его кй. Обобцениио вичаслакия и ар;ф:ет:№да второй сту-пещ/Дягебра и .„л'икп. - 1970. - Т.9, № 4. - С.375-405,

3. Его >.е. Обобщенные вшмслокня/Друды иг.тем. АН СССР. - 1973. - Т.130. - 0.59-64.

4. Его не. Об с дном кяаосс рочуроиышх иорчр*1а//Ал1г'.5зз и логика. - 1973. - 1.12, Я, - С.З-'ГГ.

5. Его ко. Обобщенные шчасле;шя над рогуляр'ил,« кудора-цияга/Ллгббра и логика. - 1073. - Т.12, И 5. - С.623.643.

6. Его кэ. О'Зобцонкне начисления и арифметика тротьзй сгупени/Дягебра и логика. - 1974» - 'Г.13, 112. - С.132-14.1.

7. Его из. Итерировавши клиииевская вычислимость и су-пзрдаями/ДСат.сб. - 1976. - Т. 101, Л. - С.21-43.

8. Его ко. Автономная вычкслдиость/'/Алгобрн я логика. -1979. - Т.'18, М. - С.398-407,

9. Его кг. 0(5 одном способе .моделирования классической арифметика второй ступени//Алгзбра и .гстака. - 1'9БЗ. - Т.22, & I. - С.3-25.

10. Его же. Взчислоная с оракуламл: гксиоматичоская версия. 4-я Воеооюз.конф. "Применение методов штепатячоокой логики", тез.дота. - Таллин. - 1986. - С,32-33.

ТТ. Его яе Еичгедения с оракулами//?рудо Ей СО АН СССР.. - 1Э89. Т.12. - С.4-24.

12, Его го. Итерированная клиниовскоя шчкелнкость,'/Саб. мат.журн, - 1989. - Т.30, 6. - С.26-41.

' 13. Его ¡т.е. Вычисления с оракулам: обобщенная еелакдйя //Сиб.пат.журя. - 1930. - Т.31, ^ 4. С.192-196.

11. Его жа. Эффэктявшо нерарг»м//Алгебра н л.-,■»: -а. -1990. - Т.23, Гг 4. - 0\3й5-357.

тб.дс^алшлм, и <у з^ой^е /.¡•¿¿■¿ели - 1>>с ¡ви> /на {¡'¿(на//&. З-флнаЬем I >1 •»'*

■МозАаи У./.- $есИоь / - - /,'д-и/

10. ра'л-л т.«., }.1 '':„!'... оол.'ы трог-ля хя.'ч,;.; 1л1г. о

орэкуламн. - Исюопс^ск: Ш СО АЛ СССР. - 1982.

ц!>гц1РУЫ Ш ЛИТЕРАТУРА

17. Ьсло«г;а П. йаутаглг&и з альтернативной теории адох-жзств. - М.: лир - 1903.

1В. тЫ'Г.за Л .II. Метпречурсмвдость адтонс.чгных нумераций/'/ Нич/ол.ггельъео сиочоуц. - Ко'аослйирок; /ЕЛ 00 АН СССР. - 1967.-ШпигЛ. -0.135-156.

15. ¿С' жо. Обобщенные зачисления с сракулимз//Алгебра к доьшл. - ЗБ8. - Т.27, '¿2. - С. 131-147.

2С. Еее Эи-Хектлвнчс сракзлн //Алгебра я логика. - 1930.

- Т. '(•■ 5. - С.637-647.

21. 1,'е аэ. Оушзравтономгме нумерации и проект друеше ср-датали/А'иг/еира и логика. - 1У91. - Т.30, Л. - С. 28-17.

22. аыоз В.Л. О^ойаешю-кокструктивпый континуум//С"б. KZV.suря. 1973. - Г.14, Г£. - С, 957-977..

23. "¡г»; Сео'З^опча.ч ечч.:слн\:ость п дескриптивная теория гаст-иотв //Сио.мт.-Г рк. - 74. - Т.15, КЗ. - С.242-261.

£4. ¿узил II.¡Т. Лвкцил ос аигдо гачос-ккх ют-лкествах и их пр.чложоцлях• - Собр.соч., Т.2, ■■ и.: К?д. ЛЯ СССР. - 1258. -С.1-1&8.

25. Нкккоароьа П.Г. Об о;;но!.': методе построения нуглераци£ //Вычйслчтальиае систвкц. - Новосибирск: ,1М СО АЛ СССР. - 19Й5.

- Зь'П. 1С7. - С.60-96.

25. Ее же. Рекурсивные иерархии, регулярные по иострое -пнл//?9Д. "Сио.глэт.лурк." - Ы., 1586. - Дел. в ВИНЖ А 5637-Зоб.

27. Ее же. Некоторые у.оди$-акац;;ц итерированной клишев-ской вц-:ис.т1ыостп//Ллгебра и лохчгка. - 1986. - Т.25, ЛС. -0.292-314.

20. Ее же. Об одно;,! обобщении аторгрованной клннчозской вкчисл;.мостк//?ед. иСпб.шт.:к;'рн." -?.!., 1986. - Дон. в

вшг.т* и 5бза-в8б. - . .

2У. Ео жз. Об одном способе рохулярцзацзя итерированной кличневсксЗ шчислитюотп //Ред. "Спб.шт.журн." - К., 19йЬ. -Доп. в ЗЛШШ Я 2696-ВЗЗ.

30. Плотникова И.А. О вычислениях с оракулами //Слб.к&т,

2'А

3ipi!. - 19ПЗ. - T.24, й I. - C.I46-I5I.

31. Пободай Л.й. Некоторые вопросы обобщенной вычаалкиои-тл//Алге0ра и логияа. - 1973. - T.I2, S 2. - 0.220-231.

32. Его но. Проблэпа остановки и теория ибгар1"<!й//'АлХ'<;,'!ра к яогаад. i- IS75. - Т. 14, 'Л 2. - ti.Iß6-203.

33. ¡Галин H.A. Конструктивные Ешцествмшио цгсла к колит-румлышо функциональная пространства //Труди штзв. лн-та ..'Л СССР. - IS62. - Т. 67. - СД5-234.

34 Jjciil P.>H!nman P.Q. iUcazáic» /А '¿/te £uf¿iju¿-,p ¿' GenezatizeJ fîecinst'ûM Theoiy - d&sietc/a и? ■■ A'ûxî', - fo/fa Üm-pj-VL

'¿b.Jíaiiltoíaíd-Ú. Я>г s upe iju ynp oa J ü e f/ui гесагИ-.а*

balito cidwai/JGekezatiuJ/?ícui$¿oíi ТЫаг« - /Ihni^u/am ■ faiiíi-НсПан4 mv- AfJ-âZ.

Ж.Hko>e S.С fîeaush't ftoiciianùà ahJ yua.niifui$ cf fihlk types !/Тгат.Лыег. No.th.5ot /dSS-ïSt-'я f-ffZ

37. Jttöc/6, Sae/fs G. В, /Veáitecuisive ids //jJjfG*6o&c Logics - /96 S - V.JO - P. J/S - 33 S.

30.cJlûsdtovoÂîs Ql ttypeiahciiijtic ptedlcatcMJ Тгаи*. Jnrsï. Jùiilt. See. - i 06 Г - и ¡¿.<3 - p.Zi -l .

39 .tJlosÀoiraklz ¿éxíams ffit Cútíoi'Jüticii Имя ties ./ Lüßk iûùôfàliiht '63'JlrîmuiaM : fÎôiM-tiùÏÏahd tifl-fí/ss-u;.y

40.Huiliez W.Comiiucbbtty âCCeSSiBÎf! d-dtUûi ti&m&Cti // Sàp&iît Logic - /965 - V. JJ - P. ¥ô -SS

41 .ftiditt W. fîaïuuiveiii iMq¡tfc otMao/s -au,/ InJudUs Jdiiiltiûiis ilLcsjit CùîÈùquii'jK^èfJ -<J;.-;Jezd¿ :■> h!ùS- fioïldh.4 15-ti - p.2t3.-2№.

42. Saci'j G. S. 7k -fseciku of И o¿¡ícb /I

eekezùèzéd fí&üzskn 7к?£п# - Jmfatf/*¿n tfmü-ttzlb'hJ

Wi - P. 8Í-93.