Обобщенно-конструктивные модели и рекурсивные иерархии Гайлит Евгения Валерьевна

Содержание к диссертации

Введение

ГЛАВА 1. Пульсирующая иерархия 24

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

2. S-множества 29

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

ГЛАВА 2. Моделирование пульсирующего процесса в рамках автономной вычислимости 46

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

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

ГЛАВА 3. Арифметика второго порядка и автономная вычислимость 61

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

2. Теория ZFC- 71

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

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

Литература 83

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

• Постановка задачи и предварительные пояснения
• Описание пульсирующего процесса
• Подготовительные рассмотрения
• Арифметика второго порядка в контексте оракульной вычислимости

Введение к работе

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

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

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

Для теории вычислений с оракулами характерно следующее:

(а) В этой теории делается повышенный акцент на оперирова-

Л ние конструктивными объектами — числами и программами.

Это избавляет от трудностей, связанных с представлением

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

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

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

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

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

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

будучи тотальным объектом, тем не менее, функционирует имен-
,fb но как частичный оракул. Н. В. Белякин впервые применил яв-

ным образом — как для описания, так и для исследования рекурсивных иерархий — оракулы, являющиеся частичными числовыми функциями. Это придает исследованиям большую прозрачность. Теория вычислений с такими оракулами и ее применения к иерархиям была развита его учениками: Л. Н. Побединым [24], В. А. Гановым [13], А. Н. Гамовой [12], Е. Г. Никифоровой [22], Р. В. Гановой [16]. Данная диссертация относится к этой же те-матике. Описание иерархий вычислимых (в обобщенном смысле) функций с применением оракулов можно найти в [9, 10].

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

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

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

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

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

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

Одним из приложений оракульной вычислимости является по
строение моделей различных теорий. Это может быть фрагмент
4g> теории множеств или арифметики конечных или трансфинитных

порядков. Задача заключается в том, чтобы либо подобрать под
ходящий оракул, моделирующий максимальный фрагмент такой
теории, либо постараться, чтобы сам оракул был бы в интуитив
ном смысле эффективен и хорошо обозрим, т. е. не слишком аб
страктен. Обычно в качестве моделируемой теории берется мате
матический анализ, представленный тем или иным способом, —
например, какой-либо вариант арифметики второго или третьего
# порядка. Нас здесь будет интересовать исключительно арифме-

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

на промежуточном этапе строить не один, а целое семейство оракулов [4]. Но в данной диссертации речи об этом не будет.

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

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

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

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

При неформальном изложении математического анализа и ря
да других математических дисциплин, аксиоматический метод
% практически не применяется. Это изложение скорее напоминает

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

**

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

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

Стандартным способом вводится гёделевская нумерация машин с оракулом. Гёделевский номер программы, как и сама программа, не зависят от оракула. Характерное свойство гёделевской нумерации заключается в том, что если дана программа машины, то можно вычислить ее гёделевский номер, и наоборот, по любому числу z можно установить, является ли z

гёделевским номером некоторой программы, и если — да, то мож-
Щ но восстановить саму программу. Это свойство позволяет ото-

ждествлять машины с геделевскими номерами их программ. В дальнейшем запись {z}^F(x) (х = (жі,... ,х_п)) будет обозначать функцию от ж, вычислимую на машине с гёделевским номером z, соединенной с оракулом F, a z будет называться F-кодом этой функции.

Обычным образом определяется F-разрешимость числовых
множеств и предикатов. Хуже обстоит дело с обобщением пере-
числимости: различные эквивалентные определения рекурсивно-
перечислимого множества при их непосредственном обобщении
на случай вычислимости с частичным оракулом перестают быть
эквивалентными. Выберем в качестве "правильного" следующее
определение. Множество А назовем F-перечислимым, если оно
есть область определения частичной jF-вычислимой функции [9].
Машину, которая F-вычисляет эту функцию, будем называть пе-
% речисляющей машиной для множества А, а ее гёделевский номер

назовем F-перечисляющим кодом.

Очевидно, множество 3(F) является F-перечислимым для любого F, где 3(F) = {(z,x) \{z}^F(x) определено}, причем перечисляющая машина может быть указана независимо от F (равномерно по F).

Через 3*(F) обозначим множество гёделевских номеров всех

машин, вычисляющих с оракулом F всюду определенные функ-

,# ции (множество -F-кодов этих функций). Это множество (3*(F))

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

Укажем еще некоторые свойства оракулов, которые нас интересуют. Основное условие — регулярность или наличие селекторного свойства, т. е. такой F-вычислимой процедуры, которая по F-коду непустого F-перечислимого множества находит некоторый его элемент. Машину, осуществляющую данную процедуру (или код этой машины) будем называть регулятором оракула F. При наличии селекции класс F-перечислимых множеств обладает привычными свойствами замкнутости относительно операций объединения и проектирования, а функция с .F-перечислимым графиком F-вычислима. И как следствие: если область определения F-вычислимой функции F-разрешима, то область значений тоже .F-разреіішма. Обо всем этом читатель может узнать из [15].

Естественным образом определяется понятие F-вычислимого дерева — как F-разрешимого множества числовых кортежей, удовлетворяющее естественному требованию: если какой-то кортеж принадлежит дереву, то любой его начальный отрезок тоже принадлежит этому дереву. Отростком T>_Vlr^_)Vk дерева V назовем множество кортежей {(щ,... ,и_п) | (г>і,... ,Vk,u%,... ,и_п) Є Т>}, при к = 1 отросток будем называть собственным.

Через T(F) обозначим множество .Р-кодов jF-вычислимых деревьев с обрывом цепей. Оракул называется слабо фундированным, если это множество F-перечислимо. Каждое z Є T(F) явля-

ется естественным обозначением некоторого ординала, т. е. высо-
<Щ ты соответствующего дерева (обозначим ее через \z\p или просто

|z|; |T(jP)| — супремум |^|). В этом смысле будем говорить о F-вычислимых ординалах. Будем пользоваться и другим представлением вычислимых ординалов в виде .F-кодов F-разрешимых диаграмм ординальных нумераций (однозначных или многозначных). Переход от одной системы обозначений к другой будет .Р-вычислимой процедурой для тех оракулов, с которыми фактически будем иметь дело. Слабая фундированность означает, что оракул наделен какой-то трансфинитной структурой. Заметим сразу, что понятие сильной фундированности было введено В. А. Гановым [13]. Впоследствии, было выяснено в работе А. Н. Гамовой [12], что вычислимость с сильно фундированным оракулом совпадает с клиниевской вычислимостью относительно некоторого функционала типа 2.

Если оракул регулярный и слабо фундированный, то с ним
% вычислим функционал Е (так называемый джамп):

0, если Э*(/?(*)=0). 1, в противном случае,

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

номеру выяснить, остановится машина или будет работать беско-

нечно. Заметим, что точно так же определяется F-вычислимость произвольного функционала типа 2, т. е. тотального отображения вида Ті —У N, где Ті = N —> N, а N — множество натуральных чисел. Дополнительный интерес представляют оракулы, которые умеют вычислять функционал Е\ (гипер-джамп).

(о, еслиУт7 3*(/?(да)=0),

Щр) - \

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

где rj(t) = {77(0),... ,77(2 — 1)). Если оракул F вычисляет Е\, то коль скоро в некотором F-вычислимом дереве обрываются все F-вычислимые цепи, то в нем обрываются все цепи.

Оракулы, обладающие вышеописанными свойствами, будут играть доминирующую роль во всех дальнейших рассмотрениях: простейшим оракулом такого вида является клиниевский оракул, релятивизованный к какому-либо G ш к произвольной тотальной функции (5. Это оракул, который (при некотором естественном кодировании задаваемых ему вопросов), представляет минимальную частичную функцию, такую, что /3 и G вычислимы с этим оракулом. Обозначим его через H^q. Более конкретно, для него должны выполняться следующие условия:

Нр,о(^¹)=Ш, (а)

ff_ftG(5"⁺¹) = G(At{j/}^(i)), (b)

если у — код Ндо-вьічислимой тотальной функции. (Мы будем подразумевать, что функционал G достаточно "сильный", т. е. функционал Е вычислим с оракулом Нр@-) Построить такой ора-

кул можно посредством итерации подходящего монотонного оператора (обозначим его A^g)- Его точное определение непосредственно извлекается из условий (а), (Ь). Такой оператор порождает трансфинитную последовательность оракулов і?"⁷, которая определяется следующим образом:

1. Я⁰ - 0.

2. Я⁷+* = A_fitG(H-r).

3. Для предельного , Я¹» = U Я⁷.

Искомый оракул H@_}g ^есть результат стабилизации этой последовательности.

Замечание. Иногда вместо (3 будем брать В — числовое множество, имея в виду его характеристическую функцию.

Всякий клиниевский оракул слабо фундирован, и если с ним вычислим функционал Е, то он регулярен [9]. В 1970 г. Н. В. Ве-лякин ввел понятие итерированной клиниевской вычислимости [1]. Она представляет собой единообразную схему "навешивания" частичных оракулов на произвольную ординальную нумерацию v. Далее мы будем иметь дело преимущественно с клиниевскими и итерированными клиниевскими оракулами, релятивизованны-ми к Е\ или к функционалу Е%, который будет определен в главе 2, когда в нем возникнет необходимость.

Приведем теперь формальное определение итерированных кли-ниевских оракулов, релятивизованных к какому-нибудь функционалу типа 2. Такие оракулы будем обозначать, как правило, через Щ_а, т ^ \v\, где v — многозначная ординальная нумера-

ция (отображение числового множества К\у\ на начальный отре-
Щі зок ординалов длины |z/|); v \ т — начальный отрезок v длины

т. Положим K_T\v\ = К\у \ г]; номерное множество ординала г < \v\ обозначим A/'J". Диаграммой нумерации v назовем множество I>] = {(г, j): vi < uj}; Т_т[р] - Г[і/ Г г].

Индукцией по г ^ \г/\ определим оракулы Щ₀ следующим образом. Пусть для а < т оракулы H*_G уже построены: тогда Щ₀ — частичная функция с минимальной областью определения, для которой выполнены условия: Условие 1. Если j Є 1С_г[р], то

,„ _% 0, если t Є графику Н"³_Г.

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

, , , 0, если І Є ЛЛ%
Я^(зЖШ) ₌ { (Ь)

#

1, в противном случае. Условие 2. Если у Є В*(Щ_>а) и А{г/}^я^(і) = /З, /З Є Т_ь то

Условие 3.

_Яг_(1₃1+(*,_У>) ₌ ,

j, если z/j минимальный ординал а < т такой, что {ж, у} П В*(Щ₀) ф 0, не определено в противном случае.

Вопросы 13¹⁺^'^ носят довольно искусственный характер и введены в определение оракула ради технического удобства. Они

обеспечивают регулярность всех оракулов Щ₀ [23]. Легко ви-
щ деть также, что все они слабо фундированы. Таким образом, все

эти оракулы вычисляют функционалы G и Е, т. е. являются естественным обобщением клиниевских оракулов, но отличие состоит в том, что Щд, сверх того, умеет разрешать предыдущие номерные множества Ы и графики Щ_а (<т < т) равномерно по і/-номерам <т.

В дополнение к сказанному, отметим: т\ < т<і ^ \и\ влечет Щ¹ С Щ². Кроме того, стоит отметить, что если нумерация v\ продолжает нумерацию z/, то для т ^ \v\, будет выполняться Щ =

Для сокращения записи, итерированные клиниевские оракулы, релятивизованные к Ei, будем обозначать Щ. Оракул H„_G будем называть замыкающим оракулом нумерации v.

Ординал г ^ \v\ называется точкой насыщения нумерации v
(относительно G), если В* (Щ_>в) = U В* (Щ₀).
% Согласно этому определению и регулярности Щ, если т — точ-

ка насыщения, В — ^-разрешимое множество, а / — вычислимая функция такая, что /: В —У )С_г[і/], то график функции / разрешим или то же самое, совокупность значений этой функции не может быть конфинальна т.

Таким образом, точки насыщения — это аналоги конструктивно-
недостижимых ординалов [28], а если нумерация эффективная в
указанном ниже смысле, то они совпадают с таковыми. Множе
ні*, ство всех этих точек насыщения обозначим 9Tq[^]. Пусть 91!^ [v\

есть множество элементов 91^ [V], являющихся предельными точ-
^ ками WL[v]. Для предельных 7 пусть 9Т'М = П УИМ. Если

г Є 9tyM — 9^+1 И' ^то ^УД^ем говорить, что г есть точка насыщения ранга 7- Множество всех точек насыщения ранга 7 обозначим через 91у[г/|. Если речь идет об эффективных нумерациях, то точки насыщения разных рангов будут ординалами разных степеней недостижимости [9, 10].

Будем говорить, что нумерация v эффективна относительно
G, если какая бы ни была нумерация v\, каждый оракул Щ₀
вычислим с оракулом Щ _G равномерно по подходящему списку
числовых параметров, характеризующих эти оракулы, а также
окрестность точки г в обеих этих нумерациях [10]. Согласно это
му определению, если г/иг/) оказались обе эффективными, то
соответствующие оракулы будут взаимно вычислимы, а поэтому,
если будем рассматривать иерархию тотальных Щд-вычислимых
функций, когда v — эффективная нумерация, то каждый класс
# этой иерархии зависит от г, а не от г/.

Простейшим частным случаем эффективных нумераций явля
ются автономные нумерации (относительно G). Всякая такая
нумерация задается генератором, т. е. парой [ги,п], где п > 0, а
w — машина такая, что для каждого очередного г множество J\f
разрешается посредством машины w (с аргументом нуль) и с ора
кулом Hyt~_TⁿQi который определяется следующим образом. Пред
полагается, что числа от 0 до п — 1 не присутствуют в нумерации
v и на шаге г используются в качестве "временных" номеров для

продолжения v X т на п шагов, так что Щл^_с является замыкающим оракулом этой продолженной нумерации. (Разумеется, коль скоро нумерация v — однозначная, то разрешение очередного номерного множества на шаге г сводится к вычислению ^-номера г.)

Предыдущее определение задает очевидный способ построения автономных нумераций. Эффективность нумераций, построенных этим способом, доказана в [5, 6]. Наряду с автономными нумерациями нам понадобятся супер автономные [14, 10]. Они отличаются от автономных тем, что иногда для порождения v-номера г разрешается пользоваться бесконечной экстраполяцией, т. е. нумерацию v f т приходится продолжить на какое-то бесконечное число шагов, при этом "временные" номера порождаются автономной процедурой вышеописанного типа. Точнее, определение суперавтономности состоит в указании для каких г это можно делать. Нужное пояснение на этот счет мы дадим, когда в этом возникнет необходимость. При соблюдении упомянутых условий в результате получается эффективная нумерация. При построении генератора для автономной или суперавтономной нумерации, когда речь идет о порождении ^-номеров точек ненасыщения можно пользоваться стандартным приемом (одним и тем же во всех случаях), а именно, для порождения zz-номера такого г используются некоторые z 6 В*{Що) — U В*(Щ_а), (например, таким

' СГ<Т '

номером может быть 3*). В дальнейшем этот прием назовем Фо-процедурой. Если имеется эффективная автономная нумерация,

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

Еще одно полезное применение процедуры Фо состоит в следующем: пусть р, — эффективная относительно Ei нумерация, т. е. навешенные на нее оракулы релятивизованы к Е\. Мы можем вместо fj, работать с нумерацией /i\, на которую навешиваются оракулы, релятивизованные к Е и которая определяется так: точку насыщения /її с порядковым номером С обозначим 5^ ^, а остальные номера строятся с помощью Фо-процедуры, соотнесенной с функционалом Е. Как показано в [9], fii тоже будет эффективной нумерацией (относительно Е). Если при этом /і была автономной относительно Еі, то /г і оказывается суперавтономной относительно Е. Аналогичный факт имеет место в более общей ситуации, например, когда мы будем работать с нумерациями, ре-лятивизованными k^jO чем пойдет речь в нужном месте.

С любым оракулом F можно связать модель языка арифметики второго порядка, состоящую из совокупности М.р тотальных, F-вычислимых функций. Этот же оракул задает модель в языке теории множеств. Предметная область этой модели (обозначим ее J\4f) будет состоять из совокупности всех так называемых jP-множєств; т. е. наследственно счетных множеств, которые естественно соответствуют F-вычислимым деревьям с обры-

вом цепей, а именно: тривиальному дереву, состоящему из одного
^ пустого кортежа, соответствует пустое множество. В противном

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

Диссертация состоит из Введения, трех глав, разбитых на параграфы, и списка литературы.

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

В первой главе посредством обобщения предложенного
Н. В. Белякиным пульсирующего процесса, строится ординаль
ная нумерация v такая, что совокупность М.у тотальных функ-
!fc ций, вычислимых с итерированным клиниевским оракулом Н„_Е

образует модель арифметики второго порядка.

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

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

%