Введение к работе
Актуальность темы. Обобщенная вычислимость - новое направление математической логики, зародившееся на стыке теории алгоритмов, теории моделей и теоретического программирования в работах Я. Москозакиса [Mos69] и X. Фридмана [Ргі71]. К данной области тесно примыкает теория допустимых множеств и HF-логика [Ваг75] и теория S-вычпслимости, разработанная Новосибирской школой [Ерш85, ГС85].
Классическая теория алгоритмов позволяет работать только с конструктивными объектами, т.е. с объектами, допускающими эффективную нумерацию натуральными числами. Однако при таком подходе многие математические построения, имеющие интуитивно алгоритмическую природу, но в неконструктивных областях (например, в полях вещественных или комплексных чисел), не являются алгоритмами с формальной точки зрения. Например, вычислительные методы математической физики, дифференциальных уравнений, математического программирования, теории вероятностей и математической статистики по сути основаны на алгоритмах, работающих с вещественными числами, последовательностями, функциями, матрицами и т.д. Суть обобщенной вычислимости заключается в распространении понятий и результатов теории алгоритмов на такие'неконструктивные области.
Неформальной интуицией обобщенной вычислимости является абстрактный вычислитель, находящийся внутри некоторого мира — алгебраической системы Л. Такой вычислитель умеет работать с элементами системы Л, организуя их финитным образом, т.е. строя из них конечные множества, списки, матрицы и т.п. К элементам Л разрешается применять операции и предикаты системы. Это элементарные шаги обобщенного алгоритма. Обобщенный алгоритм является конечным, целенаправленным, дискретным и детерминированным процессом переработки элементов системы А, т.е. обладает всеми свойствами обычного алгоритма, за исключением одного: система Л может быть неконструктивной.
Простейшая формализация этой идеи может быть получена путем введения абстрактной машины, которая может хранить во внутренней памяти конечный набор элементов системы, один шаг работы такой машины заключается в вычислении значения сигнатурного предиката, константы или операции. Такие машины под названием стандартных
схем программ впервые появились в теоретическом программировании [КС91], однако упор при этом делался на изучение сравнительной схе-матологии. Систематическое изучение обобщенной теории алгоритмов, основанное на подобных формализациях было предпринято X. Фридманом [Pri71] и Э. Блюм, С. Смейлом и М. Шубом [BSS89].
Однако, как отмечено в указанных работах, полученный таким образом класс вычислимых функций оказывается слишком мал и не совпадет с классом интуитивно вычислимых функций. В качестве решения этой проблемы многими авторами (см. обзор [КСУ89]) предлагались различные варианты успления понятая машины над системой путем введения машин со стеками, счетчиками, массивами и проч. В работе [АБМ93] изложен подход, основанный на идее А.Г. Мясникова: вместо усиления машины расширить алгебраическую систему путем перехода к списочной надстройке. Списочная надстройка, введенная [ГС85], получается добавлением к исходной системе, элементы которой называются праэ лементами, конечных последовательностей (списков) элементов системы, списков списков и т.д. вместе с набором естественных операций над списками. Машина над списочной надстройкой из [АБМ93] эквивалентна большинству существующих формализации обобщенной вычислимости: обобщенным машинам Тьюринга и схемам эффективных определений [Fri71], бесконечномерным машинам [BSS89], машинам со стеками и счетчиками [КСУ89]. Формализация из [АБМ93] принята в качестве основной в настоящей диссертации. Заметим, что Е-вычислимость яз [ГС85] отличается от рассматриваемой формализации: класс Е-вычислимых функций шире.
Имея понятие машины над алгебраической системой, можно определить основные объекты теории алгоритмов: вычислимые функции, рекурсивные и рекурсивно перечислимые множества. Уже на данном этапе появляются отличия от классической теории: класс областей определений вычислимых функций (рекурсивно перечислимые множества) не совпадает в общем случае с классом множеств значений вычислимых функций (выходные множества) [АБМ93]. Системы, в которых RE=0, т.е. классы рекурсивно перечислимых и выходных множеств совпадают, изучались в [МІ92]. В (АБМ93] построена универсальная машина для вычислимости в списочной надстройке, а также машины, вычисляющие значение произвольного терма или бескванторной формулы в рассматриваемой системе (универсальные, вычислители термов и формул). Кроме этого в [АБМ93] получено описание рекурсивно пе-
речислимых и выходных множеств формулами логики LUlU. Из него, в частности, следует, что класс выходных множеств совпадает с классом Е-определимых в HF-логике множеств. В (БМ93] анонсированы два обобщения теоремы об арифметической иерархии, а также предложен изящный способ определения Тъюринговой сводимости в обобщенном случае. Однако систематического изучения Тыоринговых степеней в обобщенной вычислимости еще не предпринималось. Цель работы. Целью диссертации являлось:
-
создание немашинлой формализации вычислимости, эквивалентной вычислимости в списочной надстройке;
-
изучение проблемы RE=0 в списочной надстройке;
-
изучение свойств Тыоринговой сводимости и Тыоринговых степеней. При этом основной упор делается на изучение вычислимости в полях вещественных, комплексных и р-адических чисел, как наиболее близких по своим алгоритмическим свойствам к арифметике.
Общая методика исследования. В основе методики исследования лежит описание рекурсивно перечислимых множеств счетными дизъюнкциями рекурсивно перечислимых наборов бескванторных формул (см. [АБМ93]) и вытекающим из этого логическим критерием Тыоринговой сводимости. Сочетание этого метода с методом приоритета используется при доказательстве обобщенной теоремы о разложении.
Практическая и теоретическая ценность. Работа носит теоретический характер. Ее результаты могут найти применение как в теории алгоритмов, так и в теоретическом программировании.
Научная новизна. Результаты работы являются новыми. Следует особо отметить доказательство обобщенной теоремы о разложении как пример применимости метода приоритета в теории рекурсии над неконструктивными системами.
Апробация. Результаты, приведенные в диссертации, докладывались и обсуждались на XI Межреспубликанской конференции по мат. логике (Казань, 1S92), на Международной конференции по мат. логике памяти А.И. Мальцева (Новосибирск, 1994), на семинаре "Логика и вычислимость'1 кафедры математической логики Омского университета (1994 - 1996 гг.).
Публикации. По теме диссертации опубликовано 6 работ, две из которых совместные. Из совместных работ в диссертации использованы результаты, полученные лично автором.
Структура и объем. Диссертация состоит из введения и трех глав, разбитых на 8 параграфов. Объем работы 69 страниц, список литературы включает 22 наименования.