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

• Автор: Гайлит, Евгения Валерьевна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Новосибирск
• Количество страниц: 87 с.

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

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

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

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

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

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

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

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

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

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

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

§ 1. Арифметика второго порядка
в контексте оракульной вычислимости
§ 2. Теория Ъ¥С~
§ 3. Связь теорий Яг и 2ЕС~
§ 4. Основная теорема
ЛИТЕРАТУРА
РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

§ 1. История вопроса
Со времен Тьюринга рассматривались вычисления со всюду определенными функциями в качестве оракулов, хотя формальное распространение этой идеи на частичные функции могло быть достигнуто за счет очевидного дополнительного соглашения. Ограничение тотальными оракулами отчасти мотивировалось направленностью исследовательских интересов на изучение теории степеней неразрешимости, которая скорее является частью обычной теории алгоритмов. При использовании частичных оракулов сходство с теорией алгоритмов заканчивается на уровне теорем об универсальной функции и о неподвижной точке. В то же время, теория частичных оракулов позволяет глубже ощутить принципи-альнз^ю разницу между тотальными и частичными вычислимыми функциями. Источник обобщенной, в том числе и оракульной, вычислимости скорее всего находится в дескриптивной теории множеств.
Для теории вычислений с оракулами характерно следующее:
(а) В этой теории делается повышенный акцент на оперирование конструктивными объектами —• числами и программами. Это избавляет от трудностей, связанных с представлением
об абстрактных объектах независимо от их описания, на что указывал еще Н. Н. Лузин [20]. Правда, числа могут быть кодами абстрактных объектов, как то: функционалов, ординалов, множеств — вычислимых с оракулом. Рассматриваемые вычисления неосуществимы практически, но можно говорить о “воображаемом” вычислении и получать значимую информацию о процессе работы соответствующих обобщенных программ.
(Ь) Сам оракул является теоретико-множественным объектом (частичной числовой функцией) и, в некотором смысле, выступает как неопределяемое понятие, описываемое аксиомами, связывающими определенным образом вопросы с ответами. Следовательно, графики этих оракулов являются объектами типа 1 (числовыми множествами или их характеристическими функциями).
Интерес к вычислениям с оракулами поддерживается исследованиями в теории рекурсивных иерархий [3]. Понятие иерархии возникло в математике независимо от теории вычислений. Если имеются некоторые простейшие объекты (например, разрешимые множества натуральных чисел, или интервалы на вещественной прямой) и набор достаточно простых, эффективных (в каком-то смысле) средств построения более сложных объектов, то возникает вопрос об изучении тех объектов, которые можно получить из простейших при помощи выбранных средств, о классификации их по сложности и т. д. Таким образом получается то, что естешего такого ординала, для которого построенная машина дает результат единицу (это и будет £*). Нахождение этого кода осуществляется с помощью машины, К-вычисляющей джамп и регулятора К. Значит код £* находится эффективно по гг, е. Как видим, такое программирование по существу происходит в рамках гиперарифметической вычислимости.
Обращаясь теперь к легко показать, что аналогичным образом равномерно по Т(К)-кодам £ (попавшим в множество А) можно найти Т(Н)-коды <т(£), а также выяснить, какой случай 1 или 2 имеет место для случае 1 найти Т(К)-код а*. Все эти вспомогательные процедуры (т. е. их К-коды) легко извлекаются из К-разрешающей процедуры для вышеупомянутой “матрицы” и в конечном итоге задаются эффективно по гг, е. Следовательно, теперь можно построить машину, которая Н-разрешает диаграмму для рассматриваемого а < тр, а так же (в случае 1) построить разрешающую машину для множества и ЛГ^а
сг*<сг'<сг ”
Напомним теперь, что навешенные на нумерацию Ьа оракулы, релятивизованы к Е. Из [9] и Н-вычислимости Е^ следует, что графики этих оракулов можно Н-разрешить равномерно по Мономерам их верхних индексов.
Следующая задача состоит в установлении равномерной Н-разрешимости всех 5-множеств, задействованных в пульсирующем процессе до момента а (назовем так для удобства упомянутые выше множества, а если имеется в виду конкретное i, то будем говорить об ^'-множествах). В схеме (*) послед-