Бесплатно скачать, заказать диплом, курсовую, диссертацию Обобщенно—конструктивные модели и рекурсивные иерарнии

У нас уже 21989 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	Обобщенно—конструктивные модели и рекурсивные иерарнии

Количество страниц	87

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23588.doc

Содержание	Содержание ВВЕДЕНИЕ... 3 § 1. История вопроса... 3 § 2. Вводные определения и обзор содержания по главам . 12 ГЛАВА 1. ПУЛЬСИРУЮЩАЯ ИЕРАРХИЯ... 24 § 1. Постановка задачи и предварительные пояснения... 26 § 2. ^-множества... 29 ш § 3. Описание пульсирующего процесса ... 34 ГЛАВА 2. МОДЕЛИРОВАНИЕ ПУЛЬСИРУЮЩЕГО ПРОЦЕССА В РАМКАХ АВТОНОМНОЙ ВЫЧИСЛИМОСТИ... 46 § 1, Подготовительные рассмотрения ... 47 § 2. Автономное моделирование ... 54 ГЛАВА 3. АРИФМЕТИКА ВТОРОГО ПОРЯДКА И ш АВТОНОМНАЯ ВЫЧИСЛИМОСТЬ... 61 § 1. Арифметика второго порядка в контексте оракульной вычислимости ... 65 § 2. Теория ZFC" ... 71 § 3. Связь теорий А2 и ZFC" ... 75 § 4. Основная теорема... 79 ЛИТЕРАТУРА ... 83 fa РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ... 87 Введение § 1. История вопроса Со времен Тьюринга рассматривались вычисления со всюду определенными функциями в качестве оракулов, хотя формальное распространение этой идеи на частичные функции могло быть достигнуто за счет очевидного дополнительного соглашения. Ограничение тотальными оракулами отчасти мотивировалось направленностью исследовательских интересов на изучение теории степеней неразрешимости, которая скорее является частью обычной теории алгоритмов. При использовании частичных оракулов сходство с теорией алгоритмов заканчивается на уровне теорем об универсальной функции и о неподвижной точке. В то же время, теория частичных оракулов позволяет глубже ощутить принципиальную разницу между тотальными и частичными вычислимыми функциями. Источник обобщенной, в том числе и оракульной, вычислимости скорее всего находится в дескриптивной теории множеств. Для теории вычислений с оракулами характерно следующее: (а) В этой теории делается повышенный акцент на оперирова- ние конструктивными объектами — числами и программами. Это избавляет от трудностей, связанных с представлением об абстрактных объектах независимо от их описания, на что указывал еще Н. Н. Лузин [20]. Правда, числа могут быть кодами абстрактных объектов, как то: функционалов, ординалов, множеств — вычислимых с оракулом. Рассматриваемые вычисления неосуществимы практически, но можно говорить о "воображаемом" вычислении и получать значимую информацию о процессе работы соответствующих обобщенных программ. (Ь) Сам оракул является теоретико-множественным объектом (частичной числовой функцией) и, в некотором смысле, выступает как неопределяемое понятие, описываемое аксиомами, связывающими определенным образом вопросы с ответами. Следовательно, графики этих оракулов являются объектами типа 1 (числовыми множествами или их характеристическими функциями). Интерес к вычислениям с оракулами поддерживается исследованиями в теории рекурсивных иерархий [3]. Понятие иерархии возникло в математике независимо от теории вычислений. Если имеются некоторые простейшие объекты (например, разрешимые множества натуральных чисел, или интервалы на вещественной прямой) и набор достаточно простых, эффективных (в каком-то смысле) средств построения более сложных объектов, то возникает вопрос об изучении тех объектов, которые можно получить из простейших при помощи выбранных средств, о классификации их по сложности и т. д. Таким образом получается то, что есте- ственно называть иерархией. Исторически первыми примерами 0 иерархий были: иерархия борелевских множеств и классификация Бэра для разрывных функций. Вначале иерархии изучались с помощью средств теоретико-множественного конструирования, а впоследствии также с использованием аппарата общей рекурсии, включая вычислимость с оракулами. Понятие частичного оракула появилось в работе С. Клини [26] в связи с обобщением рекурсивности на функционалы любых конечных типов. С. Клини допускал в качестве аргументов только тотальные функционалы, которые, в свою очередь, определены лишь на тотальных аргументах меньших типов. На первых порах представление об оракуле присутствовало в этой теории неявно, как комментарий к довольно громоздкому определению. В первоначальной версии [26] С. Клини пользуется языком рекурсивных схем для описания функций с числовыми значениями и с разнообразными аргументами конечных типов. Помимо традици-ф? онных схем суперпозиции и примитивной рекурсии, вводится еще схема, которая задает универсальную функцию для любого наперед заданного списка переменных (из-за чего с необходимостью возникают частично-вычислимые функционалы — разумеется, с тотальными аргументами). Сверх того, вводится еще одна схема (где х — ранее определенная рекурсивная функция), в которой \|\| наиболее отчетливо эксплицирована сама идея оракула. Как ви- дим, оракулом здесь оказывается сам функционал а, который, будучи тотальным объектом, тем не менее, функционирует имен- но как частичный оракул. Н. В. Белякин впервые применил явным образом — как для описания, так и для исследования рекурсивных иерархий — оракулы, являющиеся частичными числовыми функциями. Это придает исследованиям большую прозрачность. Теория вычислений с такими оракулами и ее применения к иерархиям была развита его учениками: Л. Н. Побединым [24], В. А. Гановым [13], А. Н. Гамовой [12], Е. Г. Никифоровой [22], Р. В. Гановой [16]. Данная диссертация относится к этой же те-матике. Описание иерархий вычислимых (в обобщенном смысле) функций с применением оракулов можно найти в [9, 10]. Подчеркнем, что в основе предложенного С. Клини определения лежит эффект стабилизации трансфинитного процесса, порождающего монотонно расширяющуюся совокупность функциональных равенств вида: (р(...) = Ф{-¦ ¦) или у?(...) = п. Каждое такое равенство (с подставленными в него значениями пере- менных) можно представить как объект соответствующего типа. Стабилизация этой совокупности равенств, участвующих в конкретном вычислении, обеспечивается с помощью леммы Хартогса [21]. (В версии Н. В. Белякина данный эффект эксплицирован напрямую.) Бели допускать в качестве аргументов произвольные частичные функционалы вместо тотальных, то определение было бы некорректно (могла бы нарушиться монотонность указанного процесса). Впрочем, Р. Платек [29] обобщил теорию С. Кли- ни на случай наследственно-монотонных функционалов, но здесь нет надобности в это углубляться. Сочетание двух факторов: то- тальных объектов в качестве аргументов и частичных по необходимости оракулов создает своеобразную ситуацию, разбираться в которой удобнее, если считать, что оракул — это просто соответствие между вопросами и ответами. (Иногда, правда, приходится рассматривать семейства таких оракулов.) Оба определения, как первоначально данное С. К лини, так и предложенная Н. В. Белякиным модификация, естественным образом связаны с интуитивной идеей бесконечного перебора: на-пример, оракул может быть таким, что, когда ему поступает некоторый вопрос z о вычислимой с ним (на машине z) функции а, он как-бы мгновенно перебирает все ее значения и выясняет, есть ли среди них нуль. (Ответ оракул дает только в том случае, когда ему задается вопрос о всюду определенной функции.) Этот оракул способен выполнять как простейший вид бесконечного перебора, так и "итерированный" перебор (если машина z сама задает подобные вопросы). Значит этот оракул способен итерировать джамп-оператор по всем ординалам, вычислимым с ним же. С простейшим оракулом такого типа, как известно, вычислимы в точности все П];-функции [25]. Если нас интересуют лишь тотальные вычислимые функции, то правомерно говорить о "гиперарифметической" вычислимости. Теория вычислений с частичными оракулами имеет особенности, обусловленные возможностью неполучения ответа. Если ма- шина задает оракулу вопрос, не входящий в его область определе- ния, то ответа она не получает и ее дальнейшее поведение не опре-ц, делено, т. е. машина "застревает". Таким образом, для машины г, работающей с частичным оракулом F, имеются три возможности: z останавливается, z работает бесконечно, z застревает. Для всюду определенного оракула последний случай невозможен. С появлением третьей возможности связано то, что, в отличие от обычной теории алгоритмов, проблема остановки для машин, работающих с частичным оракулом, может оказаться "полуразрешимой", т. е. оракул может оказаться способным решить следую- щую задачу. Пусть известно, что машина z не застревает, требуется выяснить, остановится она или будет работать бесконечно. Для таких оракулов естественное определение перечислимости совпадает с разрешимостью, поэтому определим F-перечислимое множество как область определения ^-вычислимой функции. Одним из приложений оракульной вычислимости является построение моделей различных теорий. Это может быть фрагмент ф теории множеств или арифметики конечных или трансфинитных порядков. Задача заключается в том, чтобы либо подобрать подходящий оракул, моделирующий максимальный фрагмент такой теории, либо постараться, чтобы сам оракул был бы в интуитивном смысле эффективен и хорошо обозрим, т. е. не слишком абстрактен. Обычно в качестве моделируемой теории берется математический анализ, представленный тем или иным способом, — например, какой-либо вариант арифметики второго или третьего ф порядка. Нас здесь будет интересовать исключительно арифме- тика второго порядка (Аъ). Как известно, в языке А% присутству-Щ, ют только числовые и функциональные переменные. Подразуме- вается, что числовые переменные пробегают натуральные числа (множество а;), а запас допустимых значений функциональных переменных варьируется в разных моделях. Важно, чтобы выполнялась схема аксиом свертывания (возможно, с некоторыми ограничениями). Другим подходящим объектом моделирования является теория ZFC~, т. е. ZFC без аксиомы степени, поскольку, как известно [8], эта аксиома ни в какой оракульной модели не выполняется. Нас будет преимущественно интересовать построение такого рода моделей языка арифметики второго порядка, в которых функциональные переменные пробегают всевозможные тотальные вычислимые с некоторым оракулом функции. Возникает вопрос: какие фрагменты теории А% можно промоделировать, если оракул обладает теми или иными свойствами и как эти свойства влияют на обширность построенной теории? Что ка-ф сается арифметики высших порядков, то в качестве допустимых значений функциональных переменных, начиная со второго типа, также можно использовать любые вычислимые тотальные объекты. Но при таком подходе в соответствующем моделируемом фрагменте теории никогда не будет выполняться, например, теорема о существовании супремума для ограниченных множеств вещественных чисел. Чтобы обойти эту трудность, приходится включать в модель не все вычислимые функционалы, а лишь спе-\|ф циально отобранные [14]. Чтобы осуществить отбор, приходится на промежуточном этапе строить не один, а целое семейство ора- кулов [4]. Но в данной диссертации речи об этом не будет. Преимущество обобщенно-конструктивных моделей заключается в том, что они представляют альтернативу аксиоматическому методу, поскольку доминирующую роль играет не логический вывод, а некое, пусть обобщенное, программирование. В свое время Д. Гильберт во введении к [17] противопоставил генетический и аксиоматический подходы. Оракульное моделирование ближе к генетическому подходу. Аксиоматический метод страдает одним существенным недостатком: он рассчитан сразу на все модели изучаемой теории. Из-за этого он становится источником многочисленных неразрешимых проблем, например, проблема континуума. Эти трудности касаются скорее не самого предмета изучения, а лишь способа его формализации. После того, как обнаружилась невозможность финитного обоснования математики, возникли компромиссные попытки обосно- вать математику какими-то псевдофинитными средствами, например, приемлемыми с точки зрения интуиционизма. Такой подход восходит к К. Геделю, который использовал для этой цели примитивно рекурсивные функционалы конечных типов. В работе К. Спектора арифметика конечных типов в полном объеме была проинтерпретирована с помощью бар-рекурсивных функционалов. Вряд ли это может служить бесспорным обоснованием математики (к чему изначально стремился Д. Гильберт). Задачи, которые преследуются оракульным моделированием, рассчитаны не на "оправдание" математики, а на исследование структуры ма-ц тематических знаний, на выявление побочных эффектов различ- ных типов их формализации. Как показал В. А. Ганов [13], на совокупности множеств, пред-ставимых объектами типа 2, вычислимыми с помощью довольно простых оракулов, выполняется континуум-гипотеза. Это созвучно с результатом К. Геделя [19], который принял аксиому конструктивности и доказал относительную непротиворечивость аксиомы выбора и обобщенной континуум-гипотезы, продемонстри-ровав, что они выполняются на классе конструктивных множеств. Таким образом, модельный универсум у К. Геделя был сконструирован при помощи принципов весьма напоминающих обобщенное программирование (правда, более общего вида, чем оракульная вычислимость). При неформальном изложении математического анализа и ряда других математических дисциплин, аксиоматический метод %- практически не применяется. Это изложение скорее напоминает описание "воображаемых" алгоритмов, исполняемых по определенной программе, содержащей какие-либо неэффективные шаги. Во многих случаях эти описания действительно вкладываются в теорию оракульной вычислимости. Встает вопрос: насколько далеко простирается эта возможность? Прояснению этого вопроса и посвящена настоящая диссертация. Предварительно напомним ряд необходимых понятий, сюда относящихся. § 2. Вводные определения и обзор содержания по главам Машина Тьюринга с оракулом представляет собой программу, которая помимо чисто вычислительных действий способна задавать вопросы на внешний выход. Оракул — это частичная числовая функция, вообще говоря, не вычислимая. Он является чем-то внешним по отношению к машине и не входит в ее состав. Од-Ш' ну и ту же машину можно соединять с различными оракулами и при этом машина может работать по-разному. Если машина, находящаяся в "вопросительном" состоянии, задала вопрос х, то от оракула ожидается ответ F(x), а если значение F(x) не определено, то работа машины прекращается, и говорят, что она застряла на вопросе х. Использование частичных оракулов имеет свои особенности, о которых было сказано в первом параграфе Введения. Вообще программирование для таких оракулов, если они обладают некоторыми добавочными свойствами, может оказаться весьма гибким и, в частности, как упоминалось, возможны некоторые виды бесконечного перебора. Стандартным способом вводится гёделевская нумерация машин с оракулом. Гёделевский номер программы, как и сама программа, не зависят от оракула. Характерное свойство гёделевской нумерации заключается в том, что если дана программа машины, то можно вычислить ее гёделевский номер, и наоборот, по любому числу z можно установить, является ли z гёделевским номером некоторой программы, и если — да, то мож-Щ но восстановить саму программу. Это свойство позволяет ото- ждествлять машины с гёделевскими номерами их программ. В дальнейшем запись {z}F(x) (а; = (х\,... ,хп)) будет обозначать функцию от аТ, вычислимую на машине с гёделевским номером я, соединенной с оракулом F, a z будет называться F-кодом этой функции. Обычным образом определяется ^-разрешимость числовых множеств и предикатов. Хуже обстоит дело с обобщением пере-числимости: различные эквивалентные определения рекурсивно-перечислимого множества при их непосредственном обобщении на случай вычислимости с частичным оракулом перестают быть эквивалентными. Выберем в качестве "правильного" следующее определение. Множество А назовем F-перечислимым, если оно есть область определения частичной ^-вычислимой функции [9]. Машину, которая F-вычисляет эту функцию, будем называть пе-Щ: речисляющей машиной для множества А, а ее гёделевский номер назовем ^-перечисляющим кодом. Очевидно, множество B(F) является F-перечислимым для любого F, где B(F) = {(z,x): {z]F{x) определено}, причем перечисляющая машина может быть указана независимо от F (равномерно по F). Через B(F) обозначим множество гёделевских номеров всех машин, вычисляющих с оракулом F всюду определенные функ- ции (множество ,Р-кодов этих функций). Это множество (B(F)) не обязано быть .F-перечислимым. Наибольший интерес, одна- ко, представляют такие оракулы, у которых это множество F-перечислимо. Укажем еще некоторые свойства оракулов, которые нас интересуют. Основное условие — регулярность или наличие селекторного свойства, т. е. такой .F-вычислимой процедуры, которая по F-коду непустого ^-перечислимого множества находит некоторый его элемент. Машину, осуществляющую данную процедуру (или код этой машины) будем называть регулятором оракула F. При наличии селекции класс .F-перечислимых множеств обладает привычными свойствами замкнутости относительно операций объединения и проектирования, а функция с .Р-перечислимым графиком ^-вычислима. И как следствие: если область определения F-вычислимой функции -F-разрешима, то область значений тоже .F-разредшма. Обо всем этом читатель может узнать из [15]. Естественным образом определяется понятие F-вычислимого дерева — как F-разрешимого множества числовых кортежей, удовлетворяющее естественному требованию: если какой-то кортеж принадлежит дереву, то любой его начальный отрезок тоже принадлежит этому дереву. Отростком Т>Уи„.>щ дерева V назовем множество кортежей {(wi,... ,un) \| (vi,... ,Ук,щ,... ,ип) ? V}, при к = 1 отросток будем называть собственным. Через T(F) обозначим множество F-кодов F-вычислимых деревьев с обрывом цепей. Оракул называется слабо фундирован- ным, если это множество F-перечислимо. Каждое z G T(F) явля- ется естественным обозначением некоторого ординала, т. е. высо- ты соответствующего дерева (обозначим ее через \z\p или просто \|г\|; \T(F)\ — супремум \z\). В этом смысле будем говорить о F-вычислимых ординалах. Будем пользоваться и другим представлением вычислимых ординалов в виде F-кодов .F-разреншмых диаграмм ординальных нумераций (однозначных или многозначных). Переход от одной системы обозначений к другой будет ^-вычислимой процедурой для тех оракулов, с которыми фактически будем иметь дело. Слабая фундированность означает, что оракул наделен какой-то трансфинитной структурой. Заметим сразу, что понятие сильной фундированности было введено В. А. Гановым [13]. Впоследствии, было выяснено в работе А. Н. Гамовой [12], что вычислимость с сильно фундированным оракулом совпадает с клиниевской вычислимостью относительно некоторого функционала типа 2. Если оракул регулярный и слабо фундированный, то с ним вычислим функционал Е (так называемый джамп): 0, если 3? (/?(?) =0), 1, в противном случае, т. е. для любой тотальной функции /3, вычислимой с этим оракулом, значение Е{0) тоже вычислимо с этим оракулом равномерно по гёделевскому номеру /3. Оракул, вычисляющий функционал Е, способен полуразрешить собственную проблему остановки: т. е. для машин, которые с ним не застревают, можно по гёделевскому номеру выяснить, остановится машина или будет работать беско- нечно. Заметим, что точно так же определяется .F-вычислимость произвольного функционала типа 2, т. е. тотального отображения вида Т\ -* N, где Т\ = N —? N, а N — множество натуральных чисел. Дополнительный интерес представляют оракулы, которые умеют вычислять функционал Е\ (гипер-джамп). 0, если \/иЗ?(Ш()) =0), 1, в противном случае, где rj(t) = (r/(0),... ,rj(t — 1)}. Если оракул F вычисляет Е\, то коль скоро в некотором F-вычислимом дереве обрываются все F-вычислимые цепи, то в нем обрываются все цепи. Оракулы, обладающие вышеописанными свойствами, будут играть доминирующую роль во всех дальнейших рассмотрениях: простейшим оракулом такого вида является клиниевскии оракул, релятивизованный к какому-либо G шк произвольной тотальной функции (3. Это оракул, который (при некотором естественном кодировании задаваемых ему вопросов), представляет минимальную частичную функцию, такую, что /3 и G вычислимы с этим оракулом. Обозначим его через H^q- Более конкретно, для него должны выполняться следующие условия: Я/г,0(2»+1) =/%), (а) если у — код Я^-вычислимой тотальной функции. (Мы будем подразумевать, что функционал G достаточно "сильный", т. е. функционал Е вычислим с оракулом Нр^.) Построить такой ора- кул можно посредством итерации подходящего монотонного опе- ратора (обозначим его Д/з,с?)- Его точное определение непосредственно извлекается из условий (а), (Ь). Такой оператор порождает трансфинитную последовательность оракулов Я7, которая определяется следующим образом: 1. Я° = 0. 3. Для предельного С, Н* = U Я7. Искомый оракул Нр q есть результат стабилизации этой после-довательности. Замечание. Иногда вместо /3 будем брать В — числовое множество, имея в виду его характеристическую функцию. Всякий клиниевский оракул слабо фундирован, и если с ним вычислим функционал Е, то он регулярен [9]. В 1970 г. Н. В. Бе-лякин ввел понятие итерированной клиниевской вычислимости [1]. Она представляет собой единообразную схему "навешивания" частичных оракулов на произвольную ординальную нумерацию v. Далее мы будем иметь дело преимущественно с клиниевскими и итерированными клиниевскими оракулами, релятивизованны-ми к Е\ или к функционалу Е%, который будет определен в главе 2, когда в нем возникнет необходимость. Приведем теперь формальное определение итерированных кли-ниевских оракулов, релятивизованных к какому-нибудь функционалу типа 2. Такие оракулы будем обозначать, как правило, через Ща, т ^ z/\|, где v — многозначная ординальная нумера-

Список литературы

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23588.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

03.11.24 Лексикографический анализ единиц поля

03.11.24 Из истории слова гость и его производных

03.11.24 Семантическое поле гость в русском языке

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

© 2006-2024. Все права защищены.
Выполнение уникальных качественных работ - от эссе и реферата до диссертации. Заказ готовых, сдававшихся ранее работ.