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

од

РОССИЙСКАЯ АКАДЕМИЯ НАУК " '" " ;(

СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С.Л.Соболева

На правах рукописи УДК 519.5<?

КОРОВИНА Маргарита Владимировна

ОБОБЩЕННАЯ ВЫЧИСЛИМОСТЬ НАД ПОЛЕМ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ

01.01.06 - математическая логика, алгебра и теория чисел

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

Новосибирск 1996

Работа выполнена в Институте математики им. С.Л.Соболева СО РАН

Научный руководитель: академик МАН ВШ,

доктор физико-математических наук, профессор С.С.Гончаров

Официальные оппоненты: доктор физико-математических наук,

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

Защита состоится " $РК.а£РЯ 1996 г. в /^"часоЕ на заседании специализированного совета Д 002.23.01 при Институте математики СО РАН

по адресу: 630090 Новосибирск, Университетский пр., 4.

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

профессор В. П. Добрица

кандидат физико-математических наук,

доцент А. А. Мальцев

Автореферат

Ученый секретарь специализированного совета Д 00 кандидат физико-математических

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИИ

Актуальность темы. Результаты диссертации относятся к обобщенной теории вычислимости. В случае классической теории алгоритмов, разработанной для дискретных структур, формализации вычислимости, предложенные Черчем, Геделем, Клини, Постом, эквивалентны. В случае же обобщенной теории вычислимости, имеющей дело с непрерывными объектами, предложены неэквивалентные подходы к вычислимости ([1,3,5-7] и др.).

Глубинной причиной неэквивалентности подходов, по-видимому, явилось то обстоятельство, что в изучаемом реальном явлении вычислимых процессов разным авторам наиболее существенным представлялись различные моменты.

В работах Ершова [3], Гончарова, Свириденко [2] была предложена концепция вычислимость = определимость^. Основная идея состоит в том, что вычислимые функции допускают формульное описание — определимость на абстрактной модели формулами, имеющими (обобщенно) эффективную семантику и названными базисными. Эта теория обобщает недетерминированную вычислимость в отличие от обобщений, основанных на расширении понятия (абстрактного) вычислительного устройства или понятия алгоритма [4].

Диссертационная работа относится к исследованиям в области теории обобщенной вычислимости и примыкает к работам [2,3].

Общая методика исследования. В диссертации используются ме-

тсды теории алгоритмов и рекурсивных функций, теории допустимых множеств и теории моделей, нестандартного анализа, а также аппарат и результаты монографий и статей [2,4,7,8].

Научная новизна. Результаты диссертации являются новыми и обоснованы доказательствами, результаты гл. 3 получены в соавторстве с О. В. Кудиновым.

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

Апробация. Результаты диссертации докладывались и анонсировались в разное время на семинарах ИМ СО РАН, НГУ, а также на 9-й Всесоюзной конференции по математической логике (Ленинград, 1988), Международном логическом коллоквиуме Клини-90 (Варна, 1990), 10-й Всесоюзной конференции по математической логике (Алма-Ата, 1990), Международной конференции по математической логике памяти А. И. Маль цева (Новосибирск, 1994).

Публикации. По теме диссертации опубликовано 7 работ [9-15].

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы из 50 наименований и занимает 108 страниц. В заключении автор выражает благодарность и признательность научному руководителю С. С. Гончарову за всестороннюю поддержку, внимание к работе и терпение, а также О. В, Кудинову, А. С. Морозову, С. П. Одинцову за обсуждения и ценные замечания.

СОДЕРЖАНИЕ РАБОТЫ

В гл. 1, 2 развивается подход, предложенный Ершовым, ^вычислимость = Е-опредслимость^>, применительно к действительным числам. Пусть R — стандартная модель вещественных чисел языкасто =< 0,1, +, •, <>. Через HW(R) обозначим наименьшее замыкание всех наследственно конечных слов (списков) с праэлементами из R. Автор придерживается определений монографии Ершова [4].

В §1 гл. 1 вводятся основные определения и доказываются свойства ^-определимых действительнозначных функций.

Сравнительный анализ с вычислимостью по Московахису (поисковой вычислимостью) [7], с выразительностью индуктивных определений (§2, 3 гл. 1) подчеркивает естественность данного подхода для непрерывных структур (в частности, действительных чисел).

В §1 гл. 2 получено описание Е-определимых действительнозначных функций на языке ч. р. ф. и алгебраических функций.

Теорема 2.1. Пусть и взаимно-однозначная конструктивизация простой модели Th(R), А универсальная функция для алгебраических функций. Тогда для любой действительнозначной ^-определимой функции / найдутся ч. р. ф. h, gr, х с0 свойствами

a) vh{2n) < f/i(2n + 1),

b) х £ (i>h(2n), vh(2n + l)) -4 f{x) = Ag{2n){x),

c) x= u(k(2n)) -> f{x) = u(X(2n)),

d) X = v(h(2n + 1)) f(x) = u{x(2n + 1)), причем {vh(2n), ¡/h(2n + 1)) С dom.Aj(S„),

(vk(2n), vh(2n + 1)) С dorn/, Une* ИО), i<h(2n + 1)) = dorn/,

(vh{£l),vh(£I+l))f}(i'h(2n),vh(&n +1)) =0 для любых I ф п.

В §2 гл. 2 рассмотрена проблема униформизации для Е-определимых предикатов на HW(R). Естественный вопрос -— допускают ли определимые множества определимые униформизации — часто возникает, например, при нахождении -СканоническогоЗ> решения у(х) некоторого уравнения f(xi у) = 0. Для E-определимых предикатов на HW{R) проблема решается положительно.

Теорема 2.2. Существует. Е- определимая функция универсальная, для частичных действительнозначных И-определилых функций.

С использованием представления действительных E-определимых функций с помощью ч.р.ф. и алгебраических функций построены абстрактные машины для вычисления действительных функций (AMR).

Стоит отметить, что, несмотря на все замечательные свойства Е-формул, отмеченные выше, у данного класса формул не хватает выразительных возможностей для описания функций, используемых достаточно широко в анализе таких как sin, ехр и др. (см. §4 гл. 1 ), степень трансцендентности которых больше нуля. Языка E-формул недостаточно для определения объектов, для которых существенными являются топологические свойства, свойства непрерывности.

В гл. 3, 4 предлагаются различные решения данной проблемы.

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

Определение 3.4. Функция f : M R вычислима, если существуют две эффективные последовательности Е-формул {Ф,(а, г, î/)},e„, {G,(a, с параметром а, найдется элементарное собственное

расширение стандартных действительных чисел R >- R со свойствами:

1. Существует t £ R такой, что t > п для любого натурального п. £. Для любого s € ы формулы Ф,(а,х,у), G,(a,x,y) задают функции /,, д„ соответственно: /,(г) = у ^ HW(HW(M) X HW(K)) t= ф.(*,г, у), д,{х) = у HW(HW(M) х HW(R) h G,{t,x,y).

3. Последовательности {f,}S£u монотонно возрастает, {<7>}jew монотонно убывают.

4. Для любого s £ ы выполняются включения ciomf, 3 Fin, domg, D

Fin.

5. Для любых s € w, x G R выполняются неравенства.

/.(*)</(*)<$.(*)•

6. /(») =y lim.-tco spf,(x) = y и liml4w sp5f,(a:) = y.

Теорема 3.3, Пусть / : И —> В, тогда следующие условия эквивалентны:

1. Существует элементарное простое расширение стандартных действительных чисел II >- В. и П-формула и определяющая функцию .Р в модели {Ш(Е), со свойством. Р | В. = /.

2. Найдется П-формула, которая в любом собственном элементарном расширении Й. >- И определяет функцию .Р со свойством Р | И = /.

3. Функция / вычислима.

Следствие 3.3. Пусть / : Л —¥ II всюду определена. Функция вычислима тогда и только тогда, когда <£надграфик^> и <£подграфик^> — Е-определимые в HW(R) множества.

Следствие 3.4, Всюду определенные вещественнозначные, непрерывные, вычислимые функции замкнуты относительно композиции.

Следствие 3.5. Пусть Ф = {/ | /: В. В., / вычислила}. Найдется вычислимая функция Р : N х В. —► И, универсальная для класса Ф.

В качестве примера вычислимых функций предложен подкласс веще-ственнозначных всюду определенных функций, допускающих мероморф-ное продолжение в С.

В гл. 4 вводится понятие слабой вычислимости на языке локальных формул. Для описания слабой вычислимости на модели К предлагается в качестве модели рассмотреть наименьшее допустимое множество над

фильтрованной структурой (К, 77,..., г„) ( (НР(К), т1,..., ту,)), а в качестве. класса формул, описывающих слабо вычислимые функции, подкласс локальных формул. Изучение свойств модели (в частности, фильтрованных полей) на языке локальных формул было предложено в работе [8].

Фомальный язык и" для работы с такими фильтрованными структурами аналогичен языку работы Циглера [8].

Определение 4.4. Пусть (Н\\'(К), ти...гп) — фильтрованная структура. Функцию / : К —^ К назовем слабо вычислимой на (Н\У(К), г1,... ту,),

если найдутся локальные формулы вида:

ет^Зт/! 6 иФ,(х,У1), (где Ф — Б -формула) со свойством

/(*) = у <НУУ(К),ти...тп) И У)-

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

Пусть ППК — ультрастепень модели К.

Теорема 4.2. Пусть <К, г„.. .т„), (HW(K), ти...тп) <ПДК, Т„..., Г„)

— фильтрованные структуры (ПдК — ультрастепень), функции г^,..., г* задают базы фильтров Т\,... ,тп соответственно.

1. Функция / : К —> К слабо вычислима на структуре (К,т1,.. .тп) тогда и только тогда, когда функция / : К —К слабо вычислима на

структуре (К, г},. ..г').

2. Функция / : К -4 К слабо вычислима на структуре (Н\У(К), т/,.. . г„ тогда и только тогда, когда функции / : К —> К слабо вычислима на структуре (НУУ(К), т),.. .г*).

3. Если функция / : К —> К слабо вычислима на структуре (К, Г;,. . . т„ то функция // Б (как образ / при естественном вложении К —> По К) слабо вычислима.

Определение 4.6 . Функционал й € 0 назовем слабо вычислимым,

если найдутся £ формула {Ф{};<„ такие, что

<ШУ(К),т,.....г„,/) И VI/ б Л(у)3у1 6 и*М>*,У1)

Теорема 4,5. Пусть (HW(R), г) — фильтрованная структура, для любого функционала (? 6 ©и следующие условия эквивалентны:

1. Функционал С слабо вычислим и ограничен.

2. Найдется эффективная последовательность вещественнознач-ных всюду определенных ^-определимых функционалов, сходящихся к <?.

В §2 гл. 4 получены характеризациониые теоремы для слабой вычислимости действительнозначных функций, функционалов на фильтрованных структурах (НР(11)т^,..., г„) с различным набором фильтров

гх,.. ., г„. Доказана теорема 5.4 о слабой вычислимости аналитических функций, заданных степенным рядом, коэффициенты которого вычислимы.

Литература

[1] Бургин М. С. Индуктивные машины Тьюринга // Докл. АН СССР. 1983. Т. 250, N 5. С. 1289-1293.

[2] Гончаров С. С., Свириденко Д. И. ¡^-программирование // Вы-числ. системы. Новосибирск, 1985. Вып. 107. С. 3-30.

[3] Ершов Ю. JI. Динамические логики над допустимыми множествами // Докл. АН СССР. 1983. Т. 273, N 5. С. 1045-1048.

[4] Ершов Ю. Л. Определимость и вычислимость. Новосибирск: Научная книга, 1996.

[5] Кушнер Б. А. Лекции по конструктивному анализу. М.: Наука, 1973,

[6] Freedman Н. Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory j/ Logic Colloquium 1969. Amsterdam: Noth-Holland, 1971. P. 361-390.

[7] Moschovakis Y. N. Foundations of the theory of algorithms // Generalized recursion theory. Amsterdam: Noth-Holland, 1986.

[8] Ziegler M. A language for topological structures which satisfies a Lindstroom-theorem // Bull. AMS. 1976. 82. P. 568-570.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[9] Коровина М. В. Действительные функции, определенные различными классами формуле списочной надстройке над действительными числами: Тез. докл. 9-й конф. по мат. логике. Ленинград, 1988. С. 78.

[10] Коровина М. В. Некоторые свойства Е-определимости: Тез. докл. 10-й конф. по мат. логике. Алма-Ата, 1990. С. 84.

[11] Коровина М. В. Обобщенная вычислимость вешественнозначных функций // Вычисл. системы. Новосибирск, 1990. Вып. 133. С. 38-68.

[12] Коровина М. В. Об универсальной рекурсивной функции и абстрактных машинах на вещественных числах со списочной надстройкой // Вычисл. системы. Новосибирск, 1996. Вып. 156.; С. 2.4 " hi

[13] Коровина М. В., Кудинов О. В. Новый подход к вычислимости вегцественнозначных функций // Вычисл. системы. Новосибирск, 1996. Вып. 156., С. 3*23

[14] Korovina M. V. Procédures for reals and uncountable structures // Abstracts of Kleene's Conf. Cofia, 1990. P. 35.

[15] Korovina M. V. Generalized computability of real functions // Siberian Adv. Math. 1992, V. 2, N 4. P. 1-18.