Обобщенно-конструктивные модели и рекурсивные иерархии тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Гайлит, Евгения Валерьевна

• Гайлит, Евгения Валерьевна
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Гайлит, Евгения Валерьевна

ВВЕДЕНИЕ.

§ 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], который принял аксиому конструктивности и доказал относительную непротиворечивость аксиомы выбора и обобщенной континуум-гипотезы, продемонстрировав, что они выполняются на классе конструктивных множеств. Таким образом, модельный универсум у К. Геделя был сконструирован при помощи принципов весьма напоминающих обобщенное программирование (правда, более общего вида, чем оракульная вычислимость).

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

Список литературы диссертационного исследования кандидат физико-математических наук Гайлит, Евгения Валерьевна, 2004 год

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.