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

На правах рукописи УДК 510.532:510.65

Гайлит Евгения Валерьевна

ОБОБЩЕННО-КОНСТРУКТИВНЫЕ МОДЕЛИ И РЕКУРСИВНЫЕ ИЕРАРХИИ

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

Автореферат

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

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

Работа выполнена на кафедре алгебры и математической логики Новосибирского государственного университета

Научный руководитель:

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

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

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

кандидат физико-математических наук, Одинцов Сергей Павлович

Ведущая организация:

Алтайский государственный университет

Защита состоится "Октября 2004 г. в "/£." ч. мин. на заседании диссертационного совета К 212.174.01 Новосибирского государственного университета по адресу: 630090, Новоси-бирск-90, ул. Пирогова, 2.

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

Автореферат разослан 15 сентября 2004 г. Ученый секретарь

диссертационного совета К 212.174.01 кандидат физико-математических наук

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

Актуальность темы. Эта тема относится к основаниям математики, понимаемым как раздел математической логики. Более конкретно, речь идет о теории обобщенно-конструктивных моделей в терминах машинно-оракульной вычислимости. Хотя такая вычислимость физически нереализуема, однако ее значимость состоит в анализе и моделировании возможных структур математического мышления. Точнее говоря, речь идет о квали-алгоритмических процедурах, в которых задействованы некоторые наиболее обозримые разновидности бесконечного перебора. Именно для этой цели используются оракулы. Такой подход в достаточно проявленном виде восходит к работам Клини [18] по теории рекурсивных функционалов и представляет собой синтез алгоритмических и теоретико-множественных методов. В конце 50-х и в 60-е годы XX века эта тема усиленно разрабатывалась особенно в зарубежной литературе: К.Спектором, Р. Плате -ком [29], Р. Ганди, П. Акцелем, Л. Харингтоном, И. Московаки-сом и другими. Несколько ближе к данной диссертации находятся работы Н. В. Белякина и его учеников: Л. Н. Победина [24], В. А. Ганова [13], А. Н. Гамовой [12], Е. Г. Никифоровой [22], Р. В. Гановой [16]. В этих работах машинно-оракульный принцип и направленность на идею бесконечного перебора выражены более явно. Такая направленность способствует лучшей экспликации связей между общей теорией вычислений и теорией иерархий, которая с начала ХХ-го века занимала видное положение в исследованиях по основаниям математики.

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

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

Вышеупомянутая экспликация находит выражение в различных подходах к формализации интуитивного понятия теоретико-множественной эффективности, восходящей к А. Лебегу и школе Н. Н. Лузина, а в последствии и к К. Геделю. Эта тема имеет особо близкое отношение к данной диссертации. Вопрос можно поставить так: какая степень эффективности пригодна для обоснования каких-либо разделов математики, преимущественно математического анализа? В этой связи особенно удобным оказалось использование частичных оракулов, поскольку оно придает повышенную гибкость языкам "обобщенного программирования". Подробнее об этом будет сказано при обзоре содержания диссертации. Использование таких машинно-оракульных языков, в частности, позволяет прояснить ситуацию с некоторыми неразрешимыми проблемами (независимыми гипотезами), которые в большом количестве возникали в свое время при теоретико-множественном изложении математики в рамках разнообразных логических исчислений. При переходе от аксиоматического подхода к обобщенно-программистскому выясняется, что проблемы эти присущи не столько предмету исследования в его интуитивно-неформальном понимании, сколько самому аксиоматическому методу и такое выяснение следует признать весьма актуальным.

Цель работы: На примере арифметики второго порядка и различных ее фрагментов, а также примыкающих разделов теории множеств, выяснить возможности переизложения математики с аксиоматического стиля на язык обобщенного программи-

рования в различных его вариациях. Непосредственной целью настоящей работы является решение следующих задач:

• Построить оракульную модель для полной арифметики второго порядка при соблюдении подходящих требований на эффективность самого процесса построения оракула.

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

• Установить невозможность такого же моделирования для полной арифметики второго порядка.

Основные результаты диссертации. Основными результатами работы являются следующие:

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

• строится автономная относительной (гипер-гипер-джампа) нумерация /г такая, что совокупность М^ тотальных функций дает модель для двухкванторного фрагмента арифметики второго порядка.

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

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

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

Апробация результатов работы. Результаты диссертации были представлены на международной школе по теории вычислимости (Новосибирск, 24-26 сентября, 2001), на международной конференции "Мальцевские чтения" (Новосибирск, 2002, 2003), на семинаре "Теория нумераций" Новосибирского государственного университета, а также на международной конференции "Алгебра и Анализ - 2004" (Казань, 2-9 июля 2004).

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

Структура и объем работы. Диссертация состоит из введения, трех глав, разбитых на параграфы, и списка литературы. Список литературы содержит 32 наименования. Общий объем диссертации 87 страниц.

Благодарности. Автор выражает свою глубокую благодарность Н. В. Белякину за научное руководство.

СОДЕРЖАНИЕ РАБОТЫ

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

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

дальнейшее поведение не определено. Вопросы и ответы кодируются натуральными числами. От свойств этого оракула зависит, какие процедуры он может исполнять. Назовем оракул ¥ регулярным, коль скоро существует Б-вычислимая процедура, выделяющая элемент из каждого непустого Б-перечислимого множества равномерно по его коду. Б-перечислимые множества — это области определения Б-вычислимых функций. Оракул ¥ слабо фундирован, если множество кодов вычислимых с этим оракулом ординалов — Б-перечислимое множество. Если оракул ¥ — регулярный и слабо фундированный, то с ними вычислим функционал Е (джамп), который можно представить как функционал типа 2:

Обозначим через Нрр (где /? — тотальная функция, а(? — функционал типа 2) минимальную частичную функцию такую, что:

где у — код Я^-вычислимой тотальной функции. Назовем Ирр юшниевскиморакулом, релятивизованным к (3, (7.

В качестве О будут использоваться функционалы Е, Е1 и Е2,

где:

Напомним также определение итерированной клиниевской вычислимости. Пусть и: }С[и] -» \и\ — ординальная нумерация, V \ т —

0, если 3* (/3(0 = 0),

1, в противном случае.

0, если У г} 3* (Р(Ш, 1)» = 0),

1, в противном случае,

0, если /3(0) € графику оракула Я/?,^,

1, в противном случае.

Е2(Р) =

начальный отрезок и длины т. Положим К,т[и] = К-[и Г г]; N1 — номерное множество ординала г < Диаграммой нумерации и назовем множество Г[д/| = {{1,7) ^ 1/]}\ Гт[г/] = Г[1/ f г].

Для г ^ \и\ индукцией по т определяется о р а кУЛК а к минимальная частичная функция, для которой выполнены усло-

Условие 1. .Если 3 £ то

з1+<0^) =

|0, если Ь € графику

[1, в противном случае,

'О, если / 6 Л^,

1, в противном случае.

(a)

(b)

Условие 2. Если у 6 В*(Н*С) и А«{у}я^(4) = /3, /? € Тх = N -У N. то Я£С(5У+1) = вф), где В*(Н^С) есть множество гёделевских номеров тотальных Я£с-вычислимых функций.

Условие 3.

если V] минимальный ординал а < г такой, что {х, у} П В*{Н^а) ф 0, не определено в противном случае.

Оракул ЩЕу будем обозначать через Щ. Оракул I будем называть замыкающим оракулом нумерации V. Точкунасыще-ния V относительно О определяем условием

ЯЧКо) = итВ*(Н°о).

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

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

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

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

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

Будем говорить, что нумерация и эффективна относительно

если какая бы ни была нумерация Vх, каждый оракул вычислим с оракулом

Простейшим частным случаем эффективных нумераций являются автономные нумерации. Всякая такая нумерация задается генератором, т. е. парой [го, тг], где п > 0, а го — машина такая, что для каждого очередного г множество М^ разрешается посредством машины и с оракулом который определяется следующим образом. Предполагается, что числа от 0 до п — 1 не присутствуют в нумерации и и на шаге г используются в качестве "временных" номеров для продолжения и [ т на п шагов, так что является замыкающим оракулом этой продолженной нумерации.

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

функций действительно дает нужную модель.

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

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

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

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

Для получения объявленного отрицательного результата необходимо продвинуть формализацию оракульной вычислимости

в рамках Ач вплоть до понятия автономной нумерации. Определение в -Аг-языке клиниевских и итерированных клиниевских оракулов, релятивизованных к Е или Ей осуществляется рутинным образом. При определении итерированной клиниевской вычислимости ординальная нумерация V рассматривается как допустимое значение функциональной переменной. Следует, однако, отметить, что в определении названных оракулов задействованы счетные ординалы. Хотя таковые можно определить в языке А2, но обращаться с ними в рамках этого языка довольно неудобно.

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

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

ЧхЗ\у(р(х,у) ->ЧиЗд (д = {(х,у) :х е ик<р(х,у)}) (ж)

(отсутствующей в Ац). Хотя не эквивалентна Ач, однако,

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

Теорема Л. Пусть оракул ¥ — регулярный, слабо фундированный. Пусть совокупность тотальных ¥-вычислимых функций образует модель арифметики второго порядка (т. е. «Мр — модель А2) и выполнимость схемы свертывания имеет место равномерно по гёделевским номерам функциональных параметров. ТогдаМр образует модель ZFC-.

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

Теорема 2. Если некоторая формула вязыке Мр-

абсолютна, то ее перевод в язык А-формул есть Мрабсолютная формула.

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

Теорема 3. Никакая автономная нумерация (относительно Е) не порождает модель А2

Данный результат допускает обобщения на случай Е- и Е2-автопомности.

ЛИТЕРАТУРА

1. Белякин Н.В., Обобщенные вычисления и арифметика второй ступени // Алгебра и логика. 1970. Т. 9, № 4. С. 375-405.

2. Белякин Н. В., Обобщенные вычисления // Труды Матем. ин.-та АН СССР. 1973. Т. 133, С. 59-64.

3. Белякин Н. В., Ободном классе рекурсивных иерархий// Алгебра и Логика. 1973. Т. 12, № 1, С. 3-21.

4. Белякин Н.В., Обобщенные вычисления и арифметика третьей ступени // Алгебра и Логика, 1974, Т. 13, № 2, С. 132-144.

5. Белякин Н. В1, Итерированная клиниевская вычислимость и суперджамп ЦМат. сб., 1976, Т. 101, № 1, С. 21-43.

6. Белякин Н. В., Автономная вычислимость // Алгебра и Логика, 1979, Т. 18, № 4, С. 398-407.

7.Белякин Н. В., Ободном способемоделирования классической арифметики второй ступени // Алгебра и Логика. 1983. Т. 22, № 1, С. 3-25.

8. Велякин Н. В., Вычисления с оракулами // Труды ИМ СО АН СССР, 1989, Т. 12, С. 4-24.

9. Белякин Н. В., Итерированная клиниевская вычислимость // Сиб. мат. журн. 1989. Т. 30, № 6. С. 27-32.

10. Белякин Н. В., Эффективные иерархии // Алгебра и логика. 1990. Т. 29, № 4. С. 385-397.

11. Белякин Н. В., Пульсирующие иерархии // Сиб. мат. журн. 1994. Т. 35, № 3. С. 520-526.

12. Гамова А. Н., Суперавтономные нумерации и проектируемые ординалы // Алгебра и логика. 1991. Т. 30, № 1. С. 28-47.

13. Ганов В. А., Обобщенно-конструктивный континуум // Сиб. мат. журн., 1973, Т. 14, № 5, С. 957-977.

14. Ганов В. А., Функционалы порядковых типов//Ред. "Сиб. мат. журн." М., 1980, Деп. в ВИНИТИ № 3230-80.

15. Ганов В. А., Белякин Н. В., Общая теория вычислений с оракулами // Новосибирск, 1989, Институт математики СОРАН.

16. Ганова Р. В., Оракульное моделирование теории множеств// Ред. "Сиб. мат. журн." Сиб. отд. РАН, — Новосибирск, 1997, — Деп. в ВИНИТИ, № 3296 — В 97.

17. Гильберт Д., Бернайс П., Основания математики. Логические исчисления и формализация арифметики // Наука, Москва, 1982.

18. Клини С. К., Введение в метаматематику. // Изд. иностр. лит., Москва, 1957.

19. Коэн Дж. П., Теория множеств и континуум-гипотеза// Москва, Мир, 1969.

20. Лузин Н. Н., Лекции об аналитических множествах и их приложениях. // Собр. соч., Т. 2, изд. АН СССР, Москва, 1958, С. 1-188.

21. Мендельсон Э., Введение в математическую логику. // Наука, Москва, 1976.

22. Никифирова Е. Г., Об одном обобщении итерированной клиниевской вычислимости, ВИНИТИ, Новосибирск, 1986 (№ 5638-

В86).

23. Никифорова Е. Г., Ободномспособе регуляризации итерированной клиниевской вычислимости// Ред. "Сиб. мат. журн." - М., 1988. - Деп. в ВИНИТИ № 2696-В88.

24. Победин Л. Н., Некоторые вопросы обобщенной вычислимости Ц Алгебра и логика, 1973, Т. 12, № 2, С. 220-231.

25. Роджерс X., Теория рекурсивных функций и эффективная вычислимость. Гл. 16 // Мир, Москва, 1972.

26. Kleene S. С, Recursive functionate and quantifiers of finite type //Trans. Amer. Math. Soc. — 1959, — V. 91, P. 1-52.

27. Kleene S. C, Turing-machine computable functionate of finite types. // Logic, Methodology and Philosophy of Science — Proceedings of the 1960 International Congress — Stanford University Press — Stanford, California, 1962, P. 38-45.

28. Kripke S., Transfinite recursion on admissible ordinals I, II // J. Symbolic Logic, 1964, vol. 29, P. 161-162.

29. Platek R., Foundations of recursion theory // Thesis. — Stanford (Calif.): Stanford University, 1966.

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

30. Гайлит Е. В., Арифметика второго порядка и пульсирующие иерархии // Сиб. мат. журн. - 2002. - Т. 43, № 1, С. 33-40.

31. Гайлит Е. В., Моделирование пульсирующего процесса // Алгебра и Логика - 2003. - Т. 42, № 6, С. 641-654.

32. Гайлит Е. В., Арифметика второго порядка и автономная вычислимость // Сиб. мат. журн., - 2003. - Т. 44, № 2, С. 303310.

33. Гайлит Е. В., Обобщенно-конструктивные модели и рекурсивные иерархии // Материалы международной конференции "Алгебра и Анализ - 2004", посвященной 200-летию Казанского университета (Казань, 2-9 июля, 2004), С. 48.

ГАЙЛИТ Евгения Валерьевна

Обобщенно-конструктивные модели и рекурсивные

иерархии

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

Подписано в печать 30.08.2004. Формат 60 X 84 1/16. Офсетная печать. Уч.-изд. л. 1. Тираж 100 экз. Заказ № 3 8 2

Лицензия ЛР № 021285 от 6 мая 1998 г. Редакционно-издательский центр НГУ 630090, Новосибирск, 90, ул. Пирогова,2

»16686

ВВЕДЕНИЕ.

§ 1. История вопроса.

§ 2. Вводные определения и обзор содержания по

главам

ГЛАВА 1. ПУЛЬСИРУЮЩАЯ ИЕРАРХИЯ.

§ 1. Постановка задачи и предварительные пояснения.

§ 2. ¿»-множества.

§ 3. Описание пульсирующего процесса

ГЛАВА 2. МОДЕЛИРОВАНИЕ ПУЛЬСИРУЮЩЕГО ПРОЦЕССА В РАМКАХ АВТОНОМНОЙ

ВЫЧИСЛИМОСТИ.

§ 1. Подготовительные рассмотрения

§ 2. Автономное моделирование

ГЛАВА 3. АРИФМЕТИКА ВТОРОГО ПОРЯДКА И

АВТОНОМНАЯ ВЫЧИСЛИМОСТЬ.

§ 1. Арифметика второго порядка в контексте оракульной вычислимости

§ 2. Теория ZFC

§ 3. Связь теорий А2 и ZFC~

§ 4. Основная теорема.

§ 1. История вопроса

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

Для теории вычислений с оракулами характерно следующее: а) В этой теории делается повышенный акцент на оперирование конструктивными объектами — числами и программами. Это избавляет от трудностей, связанных с представлением об абстрактных объектах независимо от их описания, на что указывал еще Н. Н. Лузин [20]. Правда, числа могут быть кодами абстрактных объектов, как то: функционалов, ординалов, множеств — вычислимых с оракулом. Рассматриваемые вычисления неосуществимы практически, но можно говорить о "воображаемом" вычислении и получать значимую информацию о процессе работы соответствующих обобщенных программ.

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

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

Понятие частичного оракула появилось в работе С. Клини [26] в связи с обобщением рекурсивности на функционалы любых конечных типов. С. Клини допускал в качестве аргументов только тотальные функционалы, которые, в свою очередь, определены лишь на тотальных аргументах меньших типов. На первых порах представление об оракуле присутствовало в этой теории неявно, как комментарий к довольно громоздкому определению. В первоначальной версии [26] С. Клини пользуется языком рекурсивных схем для описания функций с числовыми значениями и с разнообразными аргументами конечных типов. Помимо традиционных схем суперпозиции и примитивной рекурсии, вводится еще схема, которая задает универсальную функцию для любого наперед заданного списка переменных (из-за чего с необходимостью возникают частично-вычислимые функционалы — разумеется, с тотальными аргументами). Сверх того, вводится еще одна схема а;п+1,.) = ап+1(Х(Зп~1хфп~1, •••))> где % — ранее определенная рекурсивная функция), в которой наиболее отчетливо эксплицирована сама идея оракула. Как видим, оракулом здесь оказывается сам функционал а, который, будучи тотальным объектом, тем не менее, функционирует именно как частичный оракул. Н. В. Белякин впервые применил явным образом — как для описания, так и для исследования рекурсивных иерархий — оракулы, являющиеся частичными числовыми функциями. Это придает исследованиям большую прозрачность. Теория вычислений с такими оракулами и ее применения к иерархиям была развита его учениками: Л. Н. Побединым [24], В. А. Гановым [13], А. Н. Гамовой [12], Б. Г. Никифоровой [22], Р. В. Гановой [16]. Данная диссертация относится к этой же тематике. Описание иерархий вычислимых (в обобщенном смысле) функций с применением оракулов можно найти в [9, 10].

Подчеркнем, что в основе предложенного С. К лини определения лежит эффект стабилизации трансфинитного процесса, порождающего монотонно расширяющуюся совокупность функциональных равенств вида: <р(.) = ф(.) или ср(.) = п. Каждое такое равенство (с подставленными в него значениями переменных) можно представить как объект соответствующего типа. Стабилизация этой совокупности равенств, участвующих в конкретном вычислении, обеспечивается с помощью леммы Хартогса [21]. (В версии Н. В. Белякина данный эффект эксплицирован напрямую.) Бели допускать в качестве аргументов произвольные частичные функционалы вместо тотальных, то определение было бы некорректно (могла бы нарушиться монотонность указанного процесса). Впрочем, Р. Платек [29] обобщил теорию С. Кли-ни на случай наследственно-монотонных функционалов, но здесь нет надобности в это углубляться. Сочетание двух факторов: тотальных объектов в качестве аргументов и частичных по необходимости оракулов создает своеобразную ситуацию, разбираться в которой удобнее, если считать, что оракул — это просто соответствие между вопросами и ответами. (Иногда, правда, приходится рассматривать семейства таких оракулов.)

Оба определения, как первоначально данное С. Клини, так и предложенная Н. В. Белякиным модификация, естественным образом связаны с интуитивной идеей бесконечного перебора: например, оракул может быть таким, что, когда ему поступает некоторый вопрос 2 о вычислимой с ним (на машине х) функции а, он как-бы мгновенно перебирает все ее значения и выясняет, есть ли среди них нуль. (Ответ оракул дает только в том случае, когда ему задается вопрос о всюду определенной функции.) Этот оракул способен выполнять как простейший вид бесконечного перебора, так и "итерированный" перебор (если машина г сама задает подобные вопросы). Значит этот оракул способен итерировать джамп-оператор по всем ординалам, вычислимым с ним же. С простейшим оракулом такого типа, как известно, вычислимы в точности все П];-функции [25]. Если нас интересуют лишь тотальные вычислимые функции, то правомерно говорить о "гиперарифметической" вычислимости.

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

Одним из приложений оракульной вычислимости является построение моделей различных теорий. Это может быть фрагмент теории множеств или арифметики конечных или трансфинитных порядков. Задача заключается в том, чтобы либо подобрать подходящий оракул, моделирующий максимальный фрагмент такой теории, либо постараться, чтобы сам оракул был бы в интуитивном смысле эффективен и хорошо обозрим, т. е. не слишком абстрактен. Обычно в качестве моделируемой теории берется математический анализ, представленный тем или иным способом, — например, какой-либо вариант арифметики второго или третьего порядка. Нас здесь будет интересовать исключительно арифметика второго порядка (А2). Как известно, в языке А2 присутствуют только числовые и функциональные переменные. Подразумевается, что числовые переменные пробегают натуральные числа (множество ш), а запас допустимых значений функциональных переменных варьируется в разных моделях. Важно, чтобы выполнялась схема аксиом свертывания (возможно, с некоторыми ограничениями). Другим подходящим объектом моделирования является теория ZFC-, т. е. ZFC без аксиомы степени, поскольку, как известно [8], эта аксиома ни в какой оракульной модели не выполняется. Нас будет преимущественно интересовать построение такого рода моделей языка арифметики второго порядка, в которых функциональные переменные пробегают всевозможные тотальные вычислимые с некоторым оракулом функции. Возникает вопрос: какие фрагменты теории можно промоделировать, если оракул обладает теми или иными свойствами и как эти свойства влияют на обширность построенной теории? Что касается арифметики высших порядков, то в качестве допустимых значений функциональных переменных, начиная со второго типа, также можно использовать любые вычислимые тотальные объекты. Но при таком подходе в соответствующем моделируемом фрагменте теории никогда не будет выполняться, например, теорема о существовании супремума для ограниченных множеств вещественных чисел. Чтобы обойти эту трудность, приходится включать в модель не все вычислимые функционалы, а лишь специально отобранные [14]. Чтобы осуществить отбор, приходится на промежуточном этапе строить не один, а целое семейство оракулов [4]. Но в данной диссертации речи об этом не будет.

Преимущество обобщенно-конструктивных моделей заключается в том, что они представляют альтернативу аксиоматическому методу, поскольку доминирующую роль играет не логический вывод, а некое, пусть обобщенное, программирование. В свое время Д. Гильберт во введении к [17] противопоставил генетический и аксиоматический подходы. Оракульное моделирование ближе к генетическому подходу. Аксиоматический метод страдает одним существенным недостатком: он рассчитан сразу на все модели изучаемой теории. Из-за этого он становится источником многочисленных неразрешимых проблем, например, проблема континуума. Эти трудности касаются скорее не самого предмета изучения, а лишь способа его формализации.

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

Как показал В. А. Ганов [13], на совокупности множеств, пред-ставимых объектами типа 2, вычислимыми с помощью довольно простых оракулов, выполняется континуум-гипотеза. Это созвучно с результатом К. Геделя [19], который принял аксиому конструктивности и доказал относительную непротиворечивость аксиомы выбора и обобщенной континуум-гипотезы, продемонстрировав, что они выполняются на классе конструктивных множеств. Таким образом, модельный универсум у К. Геделя был сконструирован при помощи принципов весьма напоминающих обобщенное программирование (правда, более общего вида, чем оракульная вычислимость).

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

1. Белякин Н. В., Обобщенные вычисления и арифметика второй ступени // Алгебра и логика. 1970. Т. 9, N5 4. С. 375-405.

2. Белякин Н. В., Обобщенные вычисления // Труды Матем. ин.-та АН СССР. 1973. Т. 133, С. 59-64.

3. Белякин Н. В., Об одном классе рекурсивных иерархий // Алгебра и Логика. 1973. Т. 12, № 1, С. 3-21.

4. Белякин Н. В., Обобщенные вычисления и арифметика третьей ступени // Алгебра и Логика, 1974, т. 13, № 2, с. 132— 144.

5. Белякин Н. В., Итерированная клиниевская вычислимость и суперджамп // Мат. сб., 1976, т. 101, № 1, с. 21-43.

6. Белякин Н. В., Автономная вычислимость // Алгебра и Логика, 1979, т. 18, № 4, с. 398-407.

7. Белякин Н. В., Об одном способе моделирования классической арифметики второй ступени // Алгебра и Логика. 1983. Т. 22, № 1, С. 3-25.

8. Белякин Н. В., Вычисления с оракулами // Труды ИМ СО АН СССР, 1989, т. 12, с. 4-24.

9. Белякин Н. В., Итерированная клиниевская вычислимость // Сиб. мат. журн. 1989. Т. 30, № 6. С. 27-32.

10. Белякин Н. В., Эффективные иерархии // Алгебра и логика. 1990. Т. 29, № 4. С. 385-397.

11. Белякин Н. В., Пульсирующие иерархии // Сиб. мат. журн. 1994. Т. 35, № 3. С. 520-526.

12. Гамова А. Н., Суперавтономные нумерации и проектируемые ординалы // Алгебра и логика. 1991. Т. 30, № 1. С. 28-47.

13. Ганов В. А., Обобщенно-конструктивный континуум // Сиб. мат. журн., 1973, т. 14, № 5, с. 957-977.

14. Ганов В. А., Функционалы порядковых типов // Ред. "Сиб. мат. журн." М., 1980, Деп. в ВИНИТИ № 3230-80.

15. Ганов В. А., Белякин Н. В., Общая теория вычислений с оракулами // Новосибирск, 1989, Институт математики СОРАН.

16. Ганова Р. В., Оракульное моделирование теории множеств ¡1 Ред. "Сиб. мат. журн." Сиб. отд. РАН, — Новосибирск, 1997, — Деп. в ВИНИТИ, № 3296 — В 97.

17. Гильберт Д., Бернайс П., Основания математики. Логические исчисления и формализация арифметики // Наука, Москва, 1982.

18. Клини С. К., Введение в метаматематику. // Изд. иностр. лит., Москва, 1957.

19. Коэн Дж. П., Теория множеств и континуум-гипотез а // Москва, Мир, 1969.

20. Лузин Н. Н., Лекции об аналитических множествах и их приложениях. // Собр. соч., т. 2, изд. АИ СССР, Москва, 1958, С. 1-188.

21. Мендельсон Э., Введение в математическую логику. // Наука, Москва, 1976.

22. Никифирова Б. Г., Об одном обобщении итерированной клиниевской вычислимости, ВИНИТИ, Новосибирск, 1986 (№ 5638-В86).

23. Никифорова Е. Г., Об одном способе регуляризации итерированной клиниевской вычислимости // Ред. "Сиб. мат. журн." М., 1988. - Деп. в ВИНИТИ № 2696-В88.

24. Победин Л. Н., Некоторые вопросы обобщенной вычислимости // Алгебра и логика, 1973, т. 12, № 2, с. 220-231.

25. Роджерс X., Теория рекурсивных функций и эффективная вычислимость. Гл. 16 // Мир, Москва, 1972.

26. Kleene S. С., Recursive junctionals and quantifiers of finite type // Trans. Amer. Math. Soc. — 1959, — V. 91, P. 1-52.

27. Kleene S. C., Turing-machine computable junctionals of finite types. // Logic, Methodology and Philosophy of Science — Proceedings of the 1960 International Congress — Stanford University Press — Stanford, California, 1962, p. 38-45.

28. Kripke S., Transfinite recursion on admissible ordinals I, II // J. Symbolic Logic, 1964, vol. 29, p. 161-162.

29. Platek R., Foundations of recursion theory // Thesis. — Stanford (Calif.): Stanford University, 1966.Работы автора по теме диссертации.

30. Гайлит Е. В., Арифметика второго порядка и пульсирующие иерархии // Сиб. мат. журн. 2002. - Т. 43, № 1, С. 33-40.

31. Гайлит Е. В., Моделирование пульсирующего процесса // Алгебра и Логика 2003. - Т. 42, № б, С. 641-654.

32. Гайлит Е. В., Арифметика второго порядка и автономная вычислимость // Сиб. мат. журн., 2003. - Т. 44, № 2, с. 303310.