Алгоритмическая вычислимостьнад произвольнымиалгебраическими системами тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Министерство образования РФ Омский государственный университет

Апгаев Игорь Викторович

Алгоритмическая вычислимость над произвольными алгебраическими системами

01.01.06 — математическая логика,

Р Г 5 ОД

На правах рукописи

алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Омск-1996

Работа выполнена на кафедре математической логики и логического программирования Омского государственного университета

Научный руководитель: кандидат физико-математических наук, доцект В.Я. Беляев

Официальные оппоненты: доктор физико-математических наук, профессор A.C. Морозов доктор физико-математических наук, профессор JI.M. Мартынов

Ведущая организация: Новосибирский государственный университет

Защита состоится "22" октября 1996 г. в 15.30 на заседании елец] ализированного совета К 064.36.02 при Омском государственном ун: верситете по адресу: 644077, г. Омск, пр. Мира, 55а.

С диссертацией можно ознакомиться в библиотеке Омского госуда] ственного университета.

Автореферат разослан г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук '^

.А. Романьк<

Общая характеристика работы

Актуальность темы. Обобщенная вычислимость - новое направление математической логики, зародившееся на стыке теории алгоритмов, теории моделей и теоретического программирования в работах Я. Москозакиса [Мой69] и X. Фридмана [Рп71]. К данной области тесно примыкает теория допустимых множеств и НГ-логика [Ваг75] и теория 2-вычпслимости, разработанная Новосибирской школой [Ерш85, ГС85].

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

Неформальной интуицией обобщенной вычислимости является абстрактный вычислитель, находящийся внутри некоторого мира — алгебраической системы Л. Такой вычислитель умеет работать с элементами системы Л, организуя их финитным образом, т.е. строя из них конечные множества, списки, матрицы и т.п. К элементам А разрешается применять операции и предикаты системы. Это элементарные шаги обобщенного алгоритма. Обобщенный алгоритм является конечным, целенаправленным, дискретным и детерминированным процессом переработки элементов системы А, т.е. обладает всеми свойствами обычного алгоритма, за исключением одного: система А может быть неконструктивной.

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

схем программ впервые появились в теоретическом программировании [КС91], однако упор при этом делался на изучение сравнительной схе-матологии. Систематическое изучение обобщенной теории алгоритмов, основанное на подобных формализациях было предпринято X. Фридманом [Еп71] и Э. Блюм, С. Смейлом и М. Шубом [ВБЗвЭ].

Однако, как отмечено в указанных работах, полученный таким образом класс вычислимых функций оказывается слишком мал и не совпадет с классом интуитивно вычислимых функций. В качестве решения этой проблемы многими авторами (см. обзор [КСУ89]) предлагались различные варианты усиления понятия машины над системой путем введения машин со стеками, счетчиками, массивами и проч. В работе [АБМ93] изложен подход, основанный на идее А.Г. Мясникова: вместо усиления машины расширить алгебраическую систему путем перехода к списочной надстройке. Списочная надстройка, введенная [ГС85), получается добавлением к исходной системе, элементы которой называются праэлементами, конечных последовательностей (списков) элементов системы, списков списков и т.д. вместе с набором естественных операций над списками. Машина над списочной надстройкой из [АБМ93] эквивалентна большинству существующих формализации обобщенной вычислимости: обобщенным машинам Тьюринга и схемам эффективных определений [М71], бесконечномерным машинам [В8Э89], машинам со стеками и счетчиками [КСУ89]. Формализация из [АБМ93] принята в качестве основной в настоящей диссертации. Заметим, что Е-вычислимость из [ГС85] отличается от рассматриваемой формализации: класс Е-вычислимых функций шире.

Имея понятие машины над алгебраической системой, можно определить основные объекты теории алгоритмов: вычислимые функции, рекурсивные и рекурсивно перечислимые множества. Уже на данном этапе появляются отличия от классической теории: класс областей определений вычислимых функций (рекурсивно перечислимые множества) не совпадает в общем случае с классом множеств значений вычислимых функций (выходные множества) [АБМ93]. Системы, в которых К.Е=0, т.е. классы рекурсивно перечислимых и выходных множеств совпадают, изучались в [МЮ2]. В (АБМ93] построена универсальная машина для вычислимости в списочной надстройке, а также мапшны. вычисляющие значение произвольного терма или бескванторной формулы в рассматриваемой системе (универсальные, вычислители термов и формул). Кроме этого в [АБМ93] получено описание рекурсивно пе-

речислимых и выходных множеств формулами логики ЬЫ1Ы. Из него, в частности, следует, что класс выходных множеств совпадает с классом £-определимых в НГ-логике множеств. В (БМ93] анонсированы два обобщения теоремы об арифметической иерархии, а также предложен изящный способ определения Тъюринговой сводимости в обобщенном случае. Однако систематического изучения Тыоринговых степеней в обобщенной вычислимости еще не предпринималось.

Цель работы. Целью диссертации являлось:

1) создание немашинной формализации вычислимости, эквивалентной вычислимости в списочной надстройке;

2) изучение проблемы 11Е=0 в списочной надстройке;

3) изучение свойств Тыоринговой сводимости и Тыоринговых степеней. При этом основной упор делается на изучение вычислимости в полях вещественных, комплексных и р-адических чисел, как наиболее близких по своим алгоритмическим свойствам к арифметике.

Общая методика исследования. Б основе методики исследования лежит описание рекурсивно перечислимых множеств счетными дизъюнкциями рекурсивно перечислимых наборов бескванторных формул (см. [АБМ93]) и вытекающим из этого логическим критерием Тъюринговой сводимости. Сочетание этого метода с методом приоритета используется при доказательстве обобщенной теоремы о разложении.

Практическая и теоретическая ценность. Работа носит теоретический характер. Ее результаты могут найти применение как в теории алгоритмов, так и в теоретическом щюграммировании.

Научная новизна. Результаты работы являются новыми. Следует особо отметить доказательство обобщенной теоремы о разложении как пример применимости метода приоритета в теории рекурсии над неконструктивными системами.

Апробация. Результаты, приведенные в диссертации, докладывались и обсуждались на XI Межреспубликанской конференции по мат. логике (Казань, 1992), на Международной конференции по мат. логике памяти А.И. Мальцева (Новосибирск, 1994), на семинаре "Логика и вычислимость'1 кафедры математической логики Омского университета (1994 - 1996 гг.).

Публикации. По теме диссертации опубликовано 6 работ, две из которых совместные. Из совместных работ в диссертации использованы результаты, полученные лично автором.

Структура и объем. Диссертация состоит из введения и трех глав, разбитых на 8 параграфов. Объем работы 69 страниц, список литературы включает 22 наименования.

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

Глава I посвящена рассмотрению различных формализаций понятия вычислимости в произвольной алгебраической системе, а также свойств вычислимых функций, рекурсивных и рекурсивно перечислимых множеств. В параграфе 1 вводится класс частично рекурсивных в системе Л функций с помощью операторов суперпозиции, примитивной рекурсии и минимизации по спискам в списочной надстройке НЬ{Л). Доказывается, что класс рекурсивных в Л функций совпадает с классом В Б Б-в ы числимы х функций из [АБМ93] и классом функций, вычислимых с помощью схем эффективных определений [№71]. В этом же параграфе доказан аналог теоремы Клини о нормальной форме частично рекурсивной функции.

Теорема 2. Существуют примитивно рекурсивные функции р(х, у) и д[х,у,г) такие, что для любого г £

<рг{х) = р(х,р3(д(х,у,2) = 1)).

В §2 главы I каждому элементу списочной надстройки сопоставлены две характеристики: носитель и структура. Носитель списка а -это список всех праэлементов, из которых состоит а. Структура списка а получается заменой в а всех праэлементов на переменные. Носитель и структура однозначно описывают список. Далее введенные понятия используются для доказательства того, что вопрос об истинности формулы исчисления предикатов сигнатуры ащ в надстройке НЬ(Л) может быть сведен к истинности множества формул сигнатуры а в системе Л.

В §3 рассматривается проблема 11Е=0 в списочной надстройке. Известно (см., например, [В8889]), что понятие рекурсивно перечнслимо-го множества может быть обобщено для случая произвольной алгебраической системы двумя различными способами: как область определения рекурсивной функции (такие множества продолжают называть рекурсивно перечислимыми) и как область значений рекурсивной функции (такие множества называют выходными). В связи с этим встает вопрос поиска систем, в которых эти два класса множеств совпадают,

т.е. RE=0. Такие системы в плане алгоритмических свойств должны быть подобны натуральным числам. В [BSS89, АБМ93, Mi92] приведены некоторые такие системы, в частности, среди них поля вещественных, комплексных и /салических чисел. Заметим, что все рекурсивно перечислпмые множества могут быть эффективно занумерованы натуральными числами: Wx = dom<px, где ipz - рекурсивная функция с номером х, число х называется р.п. индексом множества Wx. Аналогичным образом могут быть занумерованы все выходные множества: Ох — гпдфх, число х - выходной индекс. В §3 рассмотрен вопрос о проблеме RE=0 в системах вида JIL(A). Теорема 4 утверждает, что если RE=0 в системе А, причем можно эффективно переходить от рекурсивно перечислимых индексов множеств к выходным и наоборот, то RE=0 и в списочной надстройке HL(A).

В главе II рассматриваются свойства полурешетки рекурсивно перечислимых Тьюринговых степеней. При этом основной упор делается на рассмотрение вычислимости в полях вещественных, комплексных и р-адических чисел. Тьюрингова сводимость определяется как в [БМ93], а именно, X <т Y, если множество X рекурсивно в системе (А,Р}, где предикат Р интерпретируется как множество Y. Изучаются свойства упорядочения рекурсивно перечислимых Тьюринговых степеней множеств X С HL{A) и упорядочения рекурсивно перечислимых пра-элементных степеней, т.е. степеней множеств Л' С А.

В §4 главы II установлено, что упорядочения праэлементных рекурсивно перечислимых Тьюринговых степеней в полях 72., С и Qp являются верхними полурешетками с наибольшим элементом. Для систем вида HL(A) это установлено в [БМ93]. В [БМ93] отмечено также, что в упорядоченном поле вещественных чисел положительно решается проблема Поста. А именно, степени множеств Q, KD (KD - канторов дисконтинуум) и X С N, X р.п. несравнимы. В теореме б доказано, что проблема Поста решается положительно и в полях комплексных и р-адических чисел.

Теорема 6. В полях С и Qp справедливы следуюь^е утверждения: N <Т Q <т AI, Q £т X для любого X С N, X £т AI, где X С N рекурсивно перечислимо, но не рекурсивно в арифметике. Кроме того, множество N ме является рекурсивным о поле Qp.

Примечательно, что доказательство не требует сложных переборных конструкций, а целиком основано на алгебраических и топологических свойствах рассматриваемых полей.

Одним из следствий отсутствия аналога канторовской спаривающей функции в полях 72. и является

Теорема 7. Пусть J- одно из полей TZ или Qp. Пусть А1„ = {(ai,... ,а„) £ F | (ai,..., а,,) алгебраически зависимы над Q}, п > 1. Тогда для всех п > 1 множества А1„ рекурсивно перечислимы и для любого X С F""1 А1„ ¿7- X.

Отсюда также следует, что существует степень, содержащая только множества, состоящие только из списков.

В §5 главы II рассматривается обобщение теоремы Сакса о разложении. Под теоремой о разложении для системы А подразумевается следующее утверждение:

Пусть В, С С. HL(A) рекурсивно перечислимые множества, причем С не рекурсивно. Тогда существуют рекурсивно перечислимые Aq,A\ такие, что

1) А0 U Ai = В, Ао Л Ai ~ 0;

2)С&Аь£ = 0,1.

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

Условие А. Существует рекурсивно перечислимая последовательность бескванторных атомных формул a 1,0$,с*з,... сигнатуры о таких, что для любой бескванторной формулы (р(х) сигнатуры а, не являющейся тождественно ложной, найдется атомная формула сц{х), что Vx (а,-(х) —» ¡р(х)) (или то же самое, что Эх (a,-(x)&<£(x))j. При этом истинность отношения Зх (а;(х)&<уэ(х)) определяется эффективно по номерам а,- и <р.

Теорема 9. Пусть система А удовлетворяет условию А и имеет разрешимую 3-теорию. Тогда для .Л справедлива теорема о разложении.

Теорема 10. Пусть система А удовлетворяет условию А, причем множество атомных формул из условия А плотно в А. Тогда для А справедлива теорема о разложении.

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

речислимое множество описывается счетной рекурсивно перечислимой дизъюнкцией бескванторных формул [АБМ93]. Поэтому рекурсивно пе-речнсшшые множества состоят тп счетного нябора частей, которые и используются в построении.

В главе III рассматриваются свойства упорядочения праэлементных Тьюринговых степеней в алгебраически замкнутых полях, рассматриваемых в сигнатуре полей. В §6 установлено, что если поле Т ненулевой степени трансцендентности над своим простым подполем, то рекурсивные над Т множества X С Т - это в точности те, которые задаются формулами вида $1(х) = О V ... V /„(х) = 0, /, - многочлены, или их дополнения. При этом нерекурсивные рекурсивно перечислимые множества представляют собой счетные множества алгебраических элементов. Поэтому каждому такому множеству может быть сопоставлено множество натуральных чисел - совокупность кодов минимальных многочленов. Получены также необходимые условия Тьюринговой сводимости праэлементных множеств в алгебраически замкнутых полях в терминах сводимости множеств их кодов в арифметике.

В §7 полученные результаты используются для доказательства того, что упорядочение праэлементных рекурсивно перечислпмых Тьюрпн-говых степеней в алгебраически замкнутых полях с трансцендентными элементами не изоморфно и не элементарно эквивалентно верхней полурешетке рекурсивно перечислимых степеней в арифметике. Это достигается при помощи рассмотрения ветвящихся и неветвящихся степеней. Рекурсивно перечислимая степень а называется ветвящейся, если существуют р.п. степени Ь, с, отличные от а, такие, что а есть наибольшая нижняя грань для {Ь,с}. В противном случае степень а неветвящаяся. В арифметике имеет место следующий результат Лахлана:

если Ь ф 0 р.п. степень, то существует неветвящаяся р.п. степень а такая, что а <т Ь (см. [Шен71'¡).

В теореме 11 устанавливается, что существует р.п. степень а > О такая, что для любой р.п. степени Ь < а степень Ь ветвящаяся.

В §8 строятся минимальные праэлементные степени в упорядочении всех Тьюринговых степеней в алгебраически замкнутых полях с трансцендентными элементами. А1т обозначает алгебраическое замыкание множества Т.

Теорема 12. Для любого множества трансцендентных элементов Т С F,T ф 0, если А1т ф F, то степень dт(А1т) является минимальной Гъюринговой степенью в Т. При этом степени ) и6г{А1тг) несравнимы, если А1тх ф А1тг.

Доказательство основано на результатах §7 и не требует переборных методов как в арифметике. Заметим, что в силу справедливости обобщенной теоремы о разложении для алгебраически замкнутых полей не существует минимальных рекурсивно перечислимых степеней.

Литература

[БМ93] Беляев В.Я., Мясников А.Г. Теоремы об иерархии в обобщенной теории рекурсии// Тез. докл. на III Международн. конф. по алгебре. Красноярск, 1993. С. 42-43.

[ГС85] Гончароа G.C., Свириденко Д.И. ^-программирование// Логико-математические проблемы МОЗ (Вычислительные системы. Вып. 107). Новосибирск, 1985. С. 3-29.

[Ерш85] Ершов Ю.Л. Ъ-определимостъ в допустимых множествах// Доклады АН СССР. 1985. N4. Т.285, 1985. С. 792794.

[КС91] Котов В.Е., Сабельфельд В.К. Теория схем программ. - М.: Наука, 1991.

[КСУ89] Кфури А. Дж., Столбоушкин А.П., Ужичин П. Некоторые открытые вопросы в теории схем программ и динамических логик// УМН. 1989. Т.44. Вып.1 (265). С. 35-55.

[Шен77] Шенфилд Дж. Степени неразрешимости. М.: Наука, 1977.

[BSS89] L. Blum, М. Shub, S. Smale. Оп а theory of computation and complexiiy over the real numbers: NP-compleieness, recursive functions and universal machines //Bull. Amer. Math. Soc. 1989. 4.21. N1. P.l-46.

[Bar75] J. Barwise. Admissible sets and structures. - Berlin: SpringerVerlag, 1975.

[Fri71] H. Friedman. Algorithmic procedures, generaiized Tating algorithms, and elementary recursion theory //Logic

Colloquium69 (R.O. Gandy and C.E.M. Yates eds), - North Holland, 1971. P. 361-390.

[Mac76] A. Macintyre. On definable subsets of p-adic numbers //The Journal of Symbolic Logic. V.4,1. 1976. N3. P. 605-610.

[Mi92] C. Michaux. Differential fields, machines over the real numbers and automata. - PhD dissertation, Universite de Mons hainaut, 1992.

[Mos69] Y. Moschovakis. Abstract first order computability 1 //Trans. Am. Math. Soc. 138 (April, 1969).

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

[АБМ92] Ашаев И.В., Беляев В.Я., Мясников А.Г. Вычислимость над алгебраическими системами //Тез. докл. на XI Межресп. конф. по логике. Казань, 1992. С. 8.

[АБМ93] Ашаев И.В., Беляев В.Я., Мясников А.Г. Подходы к теории обобщенной вычислимости// Алгебра и логика. 32. N 4 (1993). С. 349-386.

[А93] Ашаев И.В. О вычислимости над алгебраическими системами //Тез. докл. на III Международн. конф. по алгебре. Красноярск, 1993. С. 24-25.

[А9Й] Апкьев И.В. Минимальные Тьюринговы степени в обобщенной вычислгшости //Тез. докл. на Международн. конф. по мат. логике памяти А.И. Мальцева. Новосибирск, 1994. С. 13-14.

[А95] Ашаев Й.В. О вычислимости в полях //Актуальные проблемы современной математики. Т.1 - Новосибирск: йзд-во НИИ МИОО, 1995. С. 10-18.

[А96] Ашаев И.В. Теорема о разложении в обобщенной вычислимости: Препринт 96-01. Омск, 1996. С. 1-24.

Подписано в печать 10.09.96. Печ. л. 0,7. Уч.-изд. л. 0,7. Тираж 100 экз. Заказ 443. Издательско-полиграфический отдел ОмГУ - НОФ 644077, Омск-77, пр. Мира, 55а