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

Пузаренко, Вадим Григорьевич

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

Пузаренко, Вадим Григорьевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2000 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Об алгоритмических и структурных свойствах вычислимости над моделями»

Автореферат диссертации на тему "Об алгоритмических и структурных свойствах вычислимости над моделями"

На правах рукописи УДК 510.5

I 1 и

Пузаренко Вадим Григорьевич

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

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск - 2000

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

Научный руководитель:

академик РАН, доктор физико-математических наук, профессор Ершов Ю. Л.

Официальные оппоненты:

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

Ведущая организация:

Омский государственный университет

Защита состоится 16 ноября 2000 г. в Ж.

час. ьо мин. на

заседании специализированного совета Д.002.23.01 при Институте математики им. С. Л. Соболева СО РАН по адресу: 630090 Новосибирск, пр. акад. Коптюга, 4.

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

Автореферат разослан октября 2000 г.

Ученый секретарь

специализированного совета Д.002.23.01 кандидат физико-математических наук

Ряскин А. Н.

¡мг, оз

1) Актуальность темы > :

Обобщенная вычислимость — новое направление математической логики, зародившееся на стыке теории вычислимости, теории моделей и теоретического программирования в работах Я. Московакиса [23] и X. Фридмана [17].

Одним из фундаментальных вкладов математической логики в развитие математики и науки в целом стала формализация вычислимых функций и изучение их алгоритмических свойств. Эта программа получила огромный толчок в 1931 году в связи с известной теоремой Гёде-ляо неполноте, использующей понятие примитивно рекурсивной функции, и привела к появлению в течение первой половины 1930-х годов ряда определений вычислимых функций: по Черчу, Гёделю, Клини, Посту и Тьюрингу. Вскоре было доказано, что все эти определения задают один и тот же класс математических функций, который, как принято считать (согласно тезису Чёрча), состоит в точности из "эффективно вычислимых" функций. Неформально, эти функции можно вычислить с помощью современного компьютера, игнорирующего ограничения на время вычислений и используемую память. С данным понятием тесно связано понятие перечислимого подмножества множества натуральных чисел, а именно, множества, которое может быть порождено вычислимой процедурой [27].

Кроме вышеупомянутых, выделим подход Шёнфилда [26], [10], использующий абстрактные вычислительные устройства с программами, написанными на языке, близким и по духу, и по содержанию к языку АССЕМБЛЕР, а также подход ^-программирования (или семантического программирования), разработанный С.С. Гончаровым, Ю.Л. Ершовым и Д.И. Свириденко [3]. "Устройством" в семантическом программировании, в отличие от остальных формализации, в основе которых лежат алгоритмы и абстрактные вычислительные машины, служит семантика, а роль программ выполняют формулы специального вида — Е-формулы, — что позволяет определить вычислимость над абстрактной структурой ЯЛ как Х-определимость в допустимых множествах над ЭЛ. Эта идея была предложена Ю.Л. Ершовым в 1983 году [6] и нашла свое отражение в работах A.C. Морозова [22], В.А. Руднева [11], [12], М.В. Коровиной [7], О.В. Кудинова [8], А.Н. Хисамиева [14]. В связи с этим стоит упомянуть книгу Ю.Л. Ершова "Определимость и вычислимость" [4], [5], выдержавшую два издания и ставшую фудаментальной в данной области.

Примером еще одного подхода к обобщенной вычислимости служит формализация, предложенная омскими учеными И.В. Ашаевым, В.Я. Беляевым и А.Г. Мясниковым [1], использующая понятие некоторого абстрактного вычислительного устройства (В Б Б- м аш и н ы), заданного на наследственно конечной списочной надстройке над абстрактной структурой. Следуя работе [3], можно определить вычислимость над моделью Ш как Е-определимость в наследственно конечной списочной надстройке над 9Л. Отметим, что наследственно конечная списочная надстройка вычислимо эквивалентна наследственно конечной надстройке — наименьшей по включению модели теории КР1Г.

Аксиомы теории КР (происходит от начальных букв фамилий основателей Кпрке, Р1аЬек) были введены в 1966 году Платеком [25]. Он определил допустимое множество как транзитивное, непустое множество, замкнутое относительно операции ТС и удовлетворяющее До-выделению и Е-рефлексии. В 1964 году Крипке независимо ввел аналогичное понятие, заменив Е-рефлексию Е-замещением [20]. Завершающий вид теория допустимых множеств приобрела в работах Дж. Барвайса [16], [15], предложившего рассматривать допустимые множества с праэлементами (буква и в сокращении КР11 — это начальная буква слова 11ге1етеп1,). Понятия До- и Ех-формул, служащие фундаментом этой теории, были введены Леви в 1965 году [21].

С основания в начете 60-х годов, теория допустимых множеств становится основой взаимодействия между теорией модели, теорией вычислимости и теорией множеств. Перечисленные теории имеют дело, в частности, с проблемами определимости и существования множеств.

В теории допустимых множеств основное внимание уделяется изучению свойств Е-подмножеств — подмножеств, определимых Е-фор-мулами, — в отличие от классической вычислимости, где перечислимые множества * вычислимые функции являются взаимозаменяемыми. Для наследственно конечных надстроек имеется единое представление Е-подмножеств в терминах классической вычислимости.

ТЕОРЕМА 1 (вариант теоремы Вайценавичюса [2]). Пусть ШЕ(Й71) — наследственно конечная надстройка над произвольной моделью Ш. Если подмножество А С НР(М) определимо некоторой И-формулой Ф(жо), то существует вычислимая последовательность Лф = множеств, состоящих из геделевых номеров 3-формул, для которой выполняются следующие соотношения:

(г{Лф) С <г-(Ф) о

с,

Л = {Тегш(тг,5)|Э^€^((9Л,{т:т€М)) |= ¥>Ы))}- (1)

Выполняется и обратное: если для множества А существует вычислимая последовательность Л = {^4п}пбш такая, что сг(.Д) конечно и множество А представимо в виде (1), то оно определимо некоторой Ъ-формулой Фд, для которой <г(Фд) С <г+(Л).

К тому же, существует эффективная процедура нахождения по И'формуле Ф (вычислимой последовательности .4) вычислимой последовательности Аф (Е-формулы ФА).

В условии теоремы через <г+ (.4) обозначается множество сигнатурных символов, встречающихся в формулах из UА, в совокупности с сигнатурными символами наследственно конечной надстройки, а через <г~ (Ф) — множество сигнатурных символов, встречающихся в формуле Ф, без сигнатурных символов наследственно конечной надстройки. Term — бинарная функция, сопоставляющая натуральному числу п и кортежу праэлементов g элемент наследственно конечной надстройки с номером конструкции п и носителем sp (g).

С теорией допустимых множеств тесно связана теория обобщенных нумераций, предложенная Ю.Л. Ершовым в 1996 году [4]. Отличительной особенностью понятия нумерации на допустимом множестве является то, что областью определения такой нумерации может быть любое Е-подмножество данной модели, а не только весь носитель. Сводимость же осуществляется Е-предикатом (напомним, что в классической теории нумераций сводимость осуществляется вычислимой функцией). Последнее согласовывается со значением Е-предикатов в теории допустимых множеств. Так же, как и в теории вычислимости, в данной теории иногда удается воспользоваться методами классической теории нумерации для решения довольно сложных проблем. В связи с этим приведем теорему А.И. Мальцева, доказательство которой используется для решения проблемы Фридберга в теории обобщенных нумераций.

ТЕОРЕМА 2 [9]. Пусть вычислимое семейство & перечислимых множеств содержит сильно перечислимое подсемейство ©о конечных множеств такое, что

г) любое конечное подмножество Мо произвольного множества М из & содержится в подходящем конечном подмножестве Мх С М и А*1 € 60;

и) каждое множество из @о содержится в некотором строго большем множестве из &о-

Тогда заведомо существует однозначная вычислимая нумерация семейства &.

Изучение теории моделей на допустимых множеств было начато Дж. Барвайсом в 1975 году [15]. Здесь активно используется язык 9Я-логики, который является обобщением и>-логики. Отметим, что любую наследственно конечную надстройку можно рассматривать как ш-модель при естественном отождествлении множеств ординалов наследственно конечной надстройки и натуральных чисел. Техника построения моделей о;-логики, использующая понятие ^-совместности, восходит к работам Орей [24] и Хенкина [18], [19].

ТЕОРЕМА 3 (Орей). Если 5 — счетное ы-совместное множество предложений ш-логики, то 5 имеет и-систему.

ТЕОРЕМА 4 (об ы-полноте). Теория Т сигнатуры сги(Лг, (п : п < ц>)} является ш-непротиворечивой тогда и только тогда, когда она имеет ы-систему.

2) Цель работы

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

3) Научная новизна

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

4) Теоретическая и практическая ценность

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

5) Основные результаты

Автором были получены следующие результаты:

- доказана теорема о редукции для наследственно конечных надстроек над моделями регулярных теорий;

- получена дистрибутивность верхней полурешетки шЕ-степеней произвольной КРи-модели;

- установлены изоморфизмы между серией полурешеток тьюринговых и ш-степеней и соответствующими им полурешетками степеней наследственно конечных надстроек над моделями простых теорий;

- построены разрешимые вычислимые обобщенные нумерации всех £-подмножеств и всех £-функций в наследственно конечных надстройках над моделями простых теорий;

- построены однозначные вычислимые обобщенные нумерации всех Е-подмножеств и всех Е-функций в резольвентных наследственно конечных надстройках;

- получен критерий существования однозначной вычислимой обобщенной нумерации всех Е-подмножеств в классе наследственно конечных надстроек над моделями простых теорий;

- дано описание наследственно категоричных и наследственно ^-категоричных теорий.

6) Апробация работы, публикации

Факты, содержащиеся в работе, были опубликованы в [28], [29], [30], [31]. Они докладывались на XXXV Международной Студенческой Кон-

ференции (Новосибирск, 1997), на Мальцевских чтениях - 1999 (Новосибирск, 1999), на конференции Эрлогол - 1999 (Россия, 1999). Доказательство дистрибутивности верхней полурешетки вошло во 2-е издание книги Ю.Л. Ершова "Определимость и вычислимость" [5].

7) Краткое содержание

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

В главе 2 применяется идея теоремы 1 для решения ряда алгоритмических проблем: доказывается справедливость принципа редукции для наследственно конечных надстроек над моделями регулярных теорий; дано описание простых теорий (в смысле Ершова [4]) в терминах наследственно конечных надстроек над моделями этих теорий; обсуждается проблема обобщения оракульной вычислимости (в любой наследственно конечной надстройке имеется множество ординалов, по структуре и свойствам схожее с натуральными числами), и доказывается утверждение о том, что любой тьюрингов идеал реализуется в качестве семейства вычислимых подмножеств натуральных чисел на наследственно конечной надстройке над подходящим вещественно замкнутым подполем поля вещественных чисел.

Глава 3 посвящена изучению свойств обобщенных нумераций, введенных в рассмотрение Ю.Л. Ершовым в книге [4]. Сначала приведем список проблем, предлагавшихся автору, обсуждение которых нашло отражение в главе 3.

Проблема 1 (Ю.Л. Ершов, 1996) Являются ли дистрибутивными верхние полурешетки некоторых естественных семейств обобщенных нумераций?

Проблема 2 (Ю.Л. Ершов, 1996) Существует ли изоморфизм между верхними полурешетками то-степеней и тЕ-степеней допустимого множества №(5) для произвольного множества 5?

Проблема 3 (С.С. Гончаров, 1999) Привести примеры допустимых множеств, в которых существуют однозначные (разрешимые) вычислимые обобщенные нумерации семейства всех Е-подмножеств.

Решение проблемы 1 содержится в §3.1:

ПРЕДЛОЖЕНИЕ 3.1.2. Для любой всюду определенной к-нумера-ции а семейство всех классов всюду определенных А-нумераций множества 5, к которым сводится а, образует дистрибутивную верхнюю полурешетку с нулем.

ПРЕДЛОЖЕНИЕ 3.1.3. Семейство тИ-степеней всех собственных подмножеств КР11 -модели А образует дистрибутивную верхнюю полурешетку с нулем.

Вторая проблема тесно связана с первой, поскольку полурешетка т-степеней является дистрибутивной. При изучении данной проблемы автором был установлен ряд соответствий между подполурешетка-ми верхних полурешеток т-степеней и Г-степеней и соответствующими полурешетками на допустимых множествах вида 1Ш?(9Л) над моделями простых теорий конечных сигнатур.

ТЕОРЕМА 3.2.1. Пусть Ш — модель простой теории. Тогда вложение множества натуральных чисел в наследственно конечную надстройку 1№(9Я) посредством отождествления натуральных чисел с ординалами надстройки индуцирует изоморфизмы между следующими полурешетками:

а) (ЗЬу) перечислимых т-(Т-) степеней и 1Ь^(ШШ?(9Я)) (ЗЬу(ЗНПР(Ш1))) перечислимых тИ-(Т'£-)степеней допустимого множества №(ЙЯ);

б) Ъ'т (И,у) арифметических гп-(Г-)степеней и Ь^ЕЩШТ)) (Ш^ШЩЗЯ))) определимых тЕ-(ТЕ-) степеней допустимого множества Ж(9Л);

в) Ьт (ЗЬг) всех т-{Т-) степеней и идеалом ЧТ'^ {ПТТ0") полурешетки тЕ-(ТЕ-)степеней наследственно конечной надстройки Ж\ЯЯ).

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

ТЕОРЕМА 3.3.2. Пусть 9Я — модель простой теории Т конечной сигнатуры. Тогда существуют разрешимые вычислимые №(9К)-нумерации семейств всех Л-подмножеств и Е-функций.

ТЕОРЕМА 3.3.4. Пусть 1№(9Я) — резольвентная наследственно конечная надстройка над моделью конечной сигнатуры. Тогда существуют однозначные вычислимые ШШ(Ш)-нумерации семейств всех £-подмножеств и Е-функций.

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

ТЕОРЕМА 3.3.3. Для модели Ш простой теории Т конечной сигнатуры <т эквивалентны следующие условия :

1) существует однозначная вычислимая ¡№(©1)-нумерация семейства всех И-подмножеств;

2) существует однозначная вычислимая 1НЕР(ЗЛ)-нул1ераг{ия семейства всех Е-функций;

3) для любой разрешимой 1№(ЙЯ)-нул«ерачии существует однозначная, ей эквивалентная;

4) существует несущественное расширение Т" теории Т, являющееся квазижесткой.

Глава 4 посвящена изучению теоретико-модельных свойств наследственно конечных надстроек над моделями не более, чем счетных сигнатур. Было замечено, что резольвентные наследственно конечные множества в сигнатурном обогащении, в котором резольвента определяется без параметров, единственны с точностью до изоморфизма в своей теории.

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

Ответ на вопрос, как следует из примеров главы 4, отрицателен. Однако, теории таких надстроек могут быть описаны в терминах итерированных семейств ТЗ- и БТ, введенных в рассмотрение автором. Параллельно получено описание теорий, имеющих единственную с точностью до изоморфизма счетную наследственно конечную надстройку.

ТЕОРЕМА 4.2.1. Теория ТЬ(№(Ш)) является наследственно ш-ка-тегоринной в том и только в том случае, когда М<<*' £ ТТШ1. ТЕОРЕМА 4.2.2. Теория ТЬ(да(ЙЯ)) является наследственно категоричной тогда « только тогда, когда М<ш £ ТТШ1 йМе 8ТШ1.

ЛИТЕРАТУРА.

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

2. Р.Ю. Вайценавичюс, Вычислимые нумерации вычислимых функционалов на ЯЬ-допустимых множествах, Матем. логика и ее прим., Вильнюс, Ин-т мат. и киберн. АН Лит. ССР, №5, 1987, 123 -132.

3. С.С. Гончаров, Д.И. Свириденко, Е-программирование, в сб.: "Логико-математические проблемы МОЗ" (Вычислительные системы, 107), Новосибирск, Ин-т матем. СО АН СССР, 1985, 3 - 29.

4. Ю.Л. Ершов, Определимость и вычислимость, Новосибирск, Научная книга (НИИ МИОО НГУ), 1996.

5. Ю.Л. Ершов, Определимость и вычислимость, М., Экономика, Новосибирск, Научная книга, 2000.

6. Ю.Л. Ершов, Принцип Е-перечисления, Доклады АН СССР, 270, №5, 1983, 786 - 788.

7. М.В. Коровина, Об универсальной рекурсивной функции и абстрактных машинах на вещественных числах со списочной надстройкой, в сб.: "Структурные алгоритмические свойства вычислимости" (Вычислительные системы, 156), Новосибирск, Ин-т матем. СО РАН, 1996, 24 - 43.

8. М.В. Коровина, О.В. Кудинов, Новый подход к вычислимости веще-ственнозначных функций, в сб.: "Структурные алгоритмические свойства вычислимости" (Вычислительные системы, 156), Новосибирск, Инт матем. СО РАН, 1996, 3 -23.

9. А.И. Мальцев, Алгоритмы и рекурсивные функции, М., Наука, 1986.

10. A.C. Морозов, Машины Шёнфилда: методические рекомендации, Новосибирск, НГУ, 1996.

11. В.Л. Руднсз, Об универсальной рекурсивной функции на допустимых множествах, Алгебра и логика, 25, №4(1986), 425 - 435.

12. В.А. Руднев, О существовании неотделимой пары в рекурсивной теории допустимых множеств, Алгебра и логика, 27, №1(1987), 48 - 56.

13. А.И. Стукачев, Теорема об униформизации в наследственно конечных надстройках, в сб.: "Обобщенная вычислимость и определимость" (Вычислительные системы, 161), Новосибирск, Ин-т матем. СО РАН, 1998, 3 - 14.

14. А.Н. Хисамиев, Е-нумерация и S-определимость в MFx, в сб.: " Структурные алгоритмические свойства вычислимости" (Вычислительные системы, 156), Новосибирск, Ин-т матем. СО РАН, 1996, 44 -

15. J. Barwise, Admissible sets and structures, Berlin, Springer-Verlag, 1975.

16. J. Barwise, Admissible sets over Models of Set Theory, Generalized Recursion Theory, Amsterdam, North-Holland, 1974, 97 - 122.

17. H. Friedmann, Algorithmic procedures, generalized Turing algorithms and elementary recursion theory, Logic Colloqium'69 (R.O. Gandy and C.E.M. Yates eds), North-Holland, 1971, 361 - 390.

18. L. Henkin, A generalization of the concept of w-consistency, J. Symbolic Logic, 19, 1954, 183 - 196.

19. L. Henkin, A generalization of the concept of w-completeness, J. Symbolic Logic, 22, 1957, 1 - 14.

20. S. Kripke, Transfinite recursion on admissible ordinals, I, II (abstracts), J. Symbolic Logic, 33, 1964, 161 -162.

21. A. Levy, A hierarchy of formulas in set theory, Memoir Amer. Math. Soc., 57, 1965.

22. A.S. Morozov, Hyperarithmetical Functions and algebraicity, Berlin -New York, M. Arslanov and S. Lempp ed., Walter de Gruyter publ. "Recursion Theory and Complexity", Proceedings of the Kazan-97 Workshop, July 14-19 de Gruyter Series in Logic and its Applications, №2(1999), 115 - 130.

23. y. Moschovakis, Abstract first order computability 1, Trans. Amer. Math. Soc., 138 (April, 1969).

24. S. Orey, On w-consistency and related properties, J. Symbolic Logic, 21, 1956, 246 - 252.

25. R. Platck, Foundations of recursion theory, Doctoral Dissertation and Supplement, Stanford, CA: Stanford Univ., 1966.

26. J.R. Shoenfield, Recursion theory, Lecture Notes in Logic, №1, Berlin, Springer-Verlag, 1993.

27. R.I. Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Berlin, Heidelberg, New York, London, Paris, Tokyo, Springer - Verlag, 1987.

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

28. Пузаренко В.Г., О вычислимости над моделями разрешимых теорий, Алгебра и логика, 39, №2(2000), 170 - 197.

29. Пузаренко В.Г., Обобщенные нумерации и теорема Фридберга, в сб.: "Структурные и сложностные проблемы вычислимости" (Вычи-

слительные системы, 165), Новосибирск, Ин-т матем. СО РАН, 1999, 153- 176.

30. Puzarenko V.G., On computability over models of decidable theories, Algebra and models theory 2, Novosibirsk, Novosibirsk State Technical University, 1999, 94 - 103.

31. Пузаренко В.Г., О теории моделей на наследственно конечных надстройках, препринт №52, Новосибирск, ИДМИ НГУ, 2000.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Пузаренко, Вадим Григорьевич

ВВЕДЕНИЕ. 2

ГЛАВА 1. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ .!'. 11

§ 1. Общие сведения из теории допустимых множеств.—

§ 2. А-нумерации и А-конструктивизации. 22

§ 3. НЕ (91) и определимость конструкций элементов наследственно конечных надстроек. 26

§ 4. НЕ-логика как фрагмент языка . 31

§ 5. НЕ-логика как частный случай си-логики.33

ГЛАВА 2. ОБ АЛГОРИТМИЧЕСКИХ ПРОБЛЕМАХ НА НАСЛЕДСТВЕННО КОНЕЧНЫХ НАДСТРОЙКАХ.38

§ 1. Критерий Е-определимости.:. —

§2.0 принципе редукции. 42

§ 3. О характеризации простых теорий. 45

§ 4. Об обобщении оракульной вычислимости. . 50

ГЛАВА 3. ОБОБЩЕННЫЕ НУМЕРАЦИИ И СВОДИМОСТИ. 57

§ 1. Об алгебраических свойствах. —

§ 2. О сводимостях на наследственно конечных надстройках.61

§ 3. О разрешимых вычислимых А-нумерациях. 65

ГЛАВА 4. О ТЕОРИИ МОДЕЛЕЙ НА НАСЛЕДСТВЕННО КОНЕЧНЫХ НАДСТРОЙКАХ.84

§ 1. Основные определения.—

§ 2. Критерии категоричности. 86

§ 3. Примеры категоричных теорий. 93

Введение диссертация по математике, на тему "Об алгоритмических и структурных свойствах вычислимости над моделями"

В теории допустимых множеств вопросы ставить легко; искать ответы на них значительно сложнее.

Ю.Л. Ершов

Первые результаты в области вычислимости появились еще задолго до появления строгого математического понятия алгоритма. С глубокой древности до нас дошли известные многим со школьной скамьи алгоритм Евклида, "решето" Эратосфена, алгоритмы нахождения приближений трансцендентных чисел 7Г и е, метод Штурма и т. д. Одним из фундаментальных вкладов математической логики в развитие математики и науки в целом стала формализация вычислимых функций и изучение их алгоритмических свойств. Эта программа получила огромный толчок в 1931 году в связи с известной теоремой Гёделя о неполноте, использующей понятие примитивно рекурсивной функции, и привела к появлению в течение первой половины 1930-х годов ряда определений вычислимых функций: по Чёрчу, Гёделю, Клини, Посту и Тьюрингу. Вскоре было доказано, что все эти определения задают один и тот же класс математических функций, который, как принято считать (согласно тезису Чёрча), состоит в точности из "эффективно вычислимых" функций. Неформально, эти функции можно вычислить с помощью современного компьютера, игнорирующего ограничения на время вычислений и используемую память. С данным понятием тесно связано понятие перечислимого подмножества множества натуральных чисел, а именно, множества, которое может быть порождено вычислимой процедурой [34].

Кроме вышеупомянутых, выделим подход Шёнфилда [33], [13], использующий абстрактные вычислительные устройства с программами, написанными на языке, близким и по духу, и по содержанию к языку АССЕМБЛЕР, а также подход Е-программирования (или семантического программирования), разработанный С.С. Гончаровым, Ю.Л. Ершовым и Д.И. Свириденко [3]. "Устройством" в семантическом программировании, в отличие от остальных формализации, в основе которых лежат алгоритмы и абстрактные вычислительные машины, служит семантика, а роль программ выполняют формулы специального вида — Е-формулы, — что позволяет определить вычислимость над абстрактной структурой ЭДТ как Е-определимость в допустимых множествах над 971. Эта идея была предложена Ю.Л. Ершовым в 1983 году [7] и нашла свое отражение в работах A.C. Морозова [29], В.А. Руднева [15], [16], М.В. Коровиной [10], О.В. Ку-динова [11], А.Н. Хисамиева [20]. В связи с этим стоит упомянуть книгу Ю.Л. Ершова "Определимость и вычислимость" [4], [5], выдержавшую два издания и ставшую фудаментальной в данной области.

Примером еще одного подхода к обобщенной вычислимости служит формализация, предложенная омскими учеными И.В. Ашаевым, В.Я. Беляевым и А.Г. Мясниковым [1], использующая понятие некоторого абстрактного вычислительного устройства (i?.!}¿'-машины), заданного на наследственно конечной списочной надстройке над абстрактной структурой. Следуя работе [3], можно определить вычислимость над моделью DJt как Е-определимость в наследственно конечной списочной надстройке над Ш1. Отметим, что наследственно конечная списочная надстройка вычислимо эквивалентна наследственно конечной надстройке — наименьшей по включению модели теории KPU.

Аксиомы теории KP (происходит от начальных букв фамилий основателей Kripke, Platek) были введены в 1966 году Платеком [32]. Он определил допустимое множество как транзитивное, непустое множество, замкнутое относительно операции ТС и удовлетворяющее А0-выделению и Е-рефлексии. В 1964 году Крипке независимо ввел аналогичное понятие, заменив Е-рефлексию Е-замещением [27]. Завершающий вид теория допустимых множеств приобрела в работах Дж. Барвайса [23], [22], предложившего рассматривать допустимые множества с праэлементами (буква и в сокращении КРи — это начальная буква слова Цгектег^). Понятия До- и Ех-формул, служащие фундаментом этой теории, были введены Леви в 1965 году [28].

С основания в начале 60-х годов, теория допустимых множеств становится основой взаимодействия между теорией модели, теорией вычислимости и теорией множеств. Перечисленные теории имеют дело, в частности, с проблемами определимости и существования множеств.

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

ТЕОРЕМА 2.1.1 (вариант теоремы Вайценавичюса [2]). Пусть ШПР(ЭДТ) — наследственно конечная надстройка над произвольной моделью 9Я. Если подмножество А С НГ(М) определимо некоторой Е-формулой Ф(яо), то существует вычислимая последовательность Лф = {А®}пеш множеств, состоящих из геделевых номеров 3-формул, для которой выполняются соотношения а(Аф) С сг(Ф) и

А = {Тегт(п, д)|3<£> € АЦ{Ш, (т : т £ М» И ¥>Ы))}- (1)

Выполняется и обратное: если для множества А существует вычислимая последовательность А = {АГ1}пеш такая, что о~(А) конечно и множество А представимо в виде (1), то оно определимо некоторой Е-формулой Фд, для которой <г(Фд) С <т+(Д).

К тому же, существует эффективная процедура нахождения по Е-формуле Ф (вычислимой последовательности А) вычислимой последовательности Аф (Е-формулы Фд).

В условии теоремы через а+(А) обозначается множество сигнатурных символов, встречающихся в формулах из и А, в совокупности с сигнатурными символами наследственно конечной надстройки, а через сг~(Ф) — множество сигнатурных символов, встречающихся в формуле Ф, без сигнатурных символов наследственно конечной надстройки. Term — бинарная функция, сопоставляющая натуральному числу п и кортежу пра-элементов д элемент наследственно конечной надстройки с номером конструкции п и носителем sp(g).

Идея представления Е-предиката в виде вычислимой дизъюнкции 3-формул сигнатуры модели, лежащей в основании наследственно конечной надстройки, использовалась во многих работах по обобщенной вычислимости: [1], [4], [10], [19] и др. В главе 2 автор использует данный метод для решения ряда алгоритмических проблем: доказывается справедливость принципа редукции для моделей регулярных теорий; дано описание простых теорий (в смысле Ершова [4]) в терминах наследственно конечных надстроек над моделями этих теорий; обсуждается проблема обобщения оракульной вычислимости (в любой наследственно конечной надстройке имеется множество ординалов, по структуре и свойствам схожее с натуральными числами) и доказывается утверждение о том, что любой тьюрингов идеал реализуется в качестве семейства вычислимых подмножеств натуральных чисел на наследственно конечной надстройке над подходящим вещественно замкнутым подполем поля вещественных чисел.

Глава 3 посвящена изучению свойств обобщенных нумераций, введенных Ю.Л. Ершовым в книге [4]. Отличительной особенностью понятия нумерации на допустимом множестве является то, что областью определения такой нумерации может быть любое Е-подмножество данной модели, а не только весь носитель. Сводимость же осуществляется Е-предикатом (напомним, что в классической теории нумераций сводимость осуществляется вычислимой функцией). Последнее согласовывается со значением Е-предикатов в теории допустимых множеств. Сначала приведем список проблем, предлагавшихся автору, обсуждение которых нашло отражение в главе 3.

Проблема 2 (Ю.Л. Ершов, 1996) Существует ли' изоморфизм между верхними полурешетками т-степеней и т Е-степеней допустимого множества ИЕ(5') для произвольного множества 5?

Решение проблемы 1 содержится в §3.1, основными результатами которого являются следующие утверждения.

ПРЕДЛОЖЕНИЕ 3.1.1. Семейство всех классов А-нумераций подмножеств множества Я образует дистрибутивную верхнюю полурешетку с нулем.

ПРЕДЛОЖЕНИЕ 3.1.2. Для любой всюду определенной А-нумерации а семейство всех классов всюду определенных А-нумераций множества Я, к которым сводится а, образует дистрибутивную верхнюю полурешетку с нулем.

ПРЕДЛОЖЕНИЕ 3.1.3. Семейство гаЕ-степеней всех собственных подмножеств КР11-модели А образует дистрибутивную верхнюю полурешетку с нулем.

В классическом случае при доказательстве дистрибутивности верхних полурешеток нумераций (предложение 2 § 2.1[б]) неявно используется принцип униформизации, который не является справедливым в теории допустимых множеств. Автором применяется принцип Е-рефлексии, который, с одной стороны, выполняется для всех КРи-моделей, а с другой стороны, его можно рассматривать как слабый вариант принципа униформизации. К тому же, существует изоморфизм между множеством натуральных чисел и наследственно конечной надстройкой ЮТ(0), сохраняющий вычислимые свойства, поэтому метод доказательства предложения 3.1.2 можно применить и в классическом случае.

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

ТЕОРЕМА 3.2.1. Пусть ШТ — модель простой теории. Тогда вложение множества натуральных чисел в наследственно конечную надстройку ШГ(ШТ) посредством отождествления натуральных чисел с ординалами надстройки индуцирует изоморфизмы между следующими полурешетками: а) (ЗЬ^) перечислимых т-(Т-) степеней и Ь^1(И¥(Ш1)) (Юу(ШГ(Ш1))) перечислимых тХ-(ТЕ-)степеней допустимого множества НГ(ШГ); б) Ит (1УТ) арифметических т-(Т-)степеней и Ь^г(ЕШ,(9Я)) (Ь^(ЮТ(ШТ))) определимых тЕ-(ТЕ-)степеней допустимого множества в) Ьт (1<г) всех т-(Т-) степеней и идеалом Т-Ц-1^ (НТ^1) полурешетки тЕ-(ТЕ-)степеней наследственно конечной надстройки ШГ(;[ОТ).

В условии теоремы ИТ^(НТ7^) — это множество тЕ — (ГЕ—Степеней, содержащих чистые подмножества соответствующей наследственно конечной надстройки. При доказательстве этого утверждения используются как теоретико-модельные свойства, приведенные в работах [4], [9], так и вычислимые особенности моделей простых теорий, полученные в главе 2.

ТЕОРЕМА 3.3.2. Пусть ЯЛ — модель простой теории Т конечной сигнатуры. Тогда существуют разрешимые вычислимые Ш¥(Ш)-нумерации семейств всех Е-подмножеств и Е-функций.

ТЕОРЕМА 3.3.4. Пусть НЕ(ЯЯ) — резольвентная наследственно конечная надстройка над моделью Ш конечной сигнатуры. Тогда существуют однозначные вычислимые Ш¥(9Л)-нумерации семейств всех Е-подмножеств и Т,-функций.

Теоремы 3.3.2 и 3.3.4 доказываются путем сведения к следующему утверждению [12].

ТЕОРЕМА. Пусть вычислимое семейство & перечислимых множеств содержит сильно перечислимое подсемейство ©о конечных множеств такое, что г) любое конечное подмножество Мо произвольного множества М из & содержится в подходящем конечном подмножестве М\ С Ми Мх 6 60/ гг) каждое множество из &о содержится в некотором строго большем множестве из ©о

Тогда заведомо существует однозначная вычислимая нумерация семейства &.

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

ТЕОРЕМА 3.3.3. Для модели простой теории Т конечной сигнатуры а эквивалентны следующие условия :

1) существует однозначная вычислимая Ш¥(9Л)-нумерация семейства всех Е-подмножеств;

2) существует однозначная вычислимая НЕ(9Л)-нумерация семейства всех Т,-функций;

3) для любой разрешимой {УК)-нумерации существует однозначная, ей эквивалентная;

4) существует несущественное расширение Т' теории Т, являющееся квазижестким.

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

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

Ответ на вопрос, как следует из примеров главы 4, отрицателен. Однако, теории таких надстроек могут быть описаны в терминах итерированных семейств ТЗ- и Б У7. Данные семейства строятся с помощью определимого объединения по счетным ординалам из подмножеств, являющихся объединением конечного числа полных подмножеств, и конечных подмножеств соответственно. Параллельно получено описание теорий, имеющих единственную с точностью до изоморфизма счетную наследственно конечную надстройку.

ТЕОРЕМА 4.2.1. Теория Th(HF(3tt)) является наследственно ш-кате-горичной в том и только в том случае, когда М<ш £ TJ-Wl ■ ТЕОРЕМА 4.2.2. Теория Th(HF(£DT)) является наследственно категоричной в том и только в том случае, когда М<ш £ и М £ ЭТШХ.

В доказательстве применяется техника построения моделей и-логики, использующая понятие w-совместности, которая восходит к работам Орей [31] и Хенкина [25], [26]. Как уже ранее отмечалось, любую наследственно конечную надстройку можно рассматривать как си-модель при естественном отождествлении множеств ординалов наследственно конечной надстройки и натуральных чисел. В теории моделей над допустимыми множествами активно используется язык £РТ-логики, который является обобщением ш-логики [22].

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

Пользуясь случаем, автор выражает благодарность Ю.Л. Ершову, под чьим руководством и влиянием была выполнена данная работа, С.С. Гончарову за постановку задачи, решенной в рамках гранта "Университеты России", A.C. Морозову за обсуждение результатов главы 4 и ценные замечания, позволившие улучшить ее изложение, О.В. Кудинову за оказанную помощь в оформлении результатов § 3.3, а также всем участникам семинаров "Алгебра и логика" и "Теория нумераций". Особая признательность молодым сотрудникам и аспирантам кафедры алгебры и математической логики Новосибирского Государственного Университета за помощь на завершающем этапе оформления текста диссертации.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Пузаренко, Вадим Григорьевич, Новосибирск

2. Р.Ю. Вайценавичюс, Вычислимые нумерации вычислимых функционалов на RL-допустимых множествах, Матем. логика и ее прим., Вильнюс, Ин-т мат. и киберн. АН Лит. ССР, №5, 1987, 123 -132.

4. Ю.Л. Ершов, Определимость и вычислимость, Новосибирск, Научная книга (НИИ МИ00 НГУ), 1996.

5. Ю.Л. Ершов, Определимость и вычислимость, М., Экономика, Новосибирск, Научная книга, 2000.

6. Ю.Л. Ершов, Теория нумераций, М., Наука, 1977.

7. Ю.Л. Ершов, Принцип Е-перечисления, Доклады АН СССР, 270, №5, 1983, 792 794.

8. Ю.Л. Ершов, Проблемы разрешимости и конструктивные модели, М., Наука, 1980.

9. Г. Кейслер , Ч.Ч. Чен , Теория моделей, М., Мир, 1977.

10. М.В. Коровина, О.В. Кудинов, Новый подход к вычислимости веще-ственнозначных функций, в сб.: "Структурные алгоритмические свойства вычислимости" (Вычислительные системы, 156), Новосибирск, Ин-т матем. СО РАН, 1996, 3 -23.

11. А.И. Мальцев, Алгоритмы и рекурсивные функции, М., Наука, 1986.

12. A.C. Морозов, Машины Шёнфилда: методические рекомендации, Новосибирск, НГУ, 1996.

13. X. Роджерс, Теория рекурсивных функций и эффективная вычислимость, Москва, Мир, 1972.

14. В.А. Руднев, Об универсальной рекурсивной функции на допустимых множествах, Алгебра и логика, 25, №4(1986), 425 435.

15. В.А. Руднев, О существовании неотделимой пары в рекурсивной теории допустимых множеств, Алгебра и логика, 27, JYfil(1987), 48 56.

16. Док.Е. Сакс, Теория насыщенных моделей, М., Мир, 1976.

17. Справочная книга по математической логике, под ред. Дж. Барвайса, часть 1, М., Наука, 1982.

18. А.И. Стукачев, Теорема об униформизации в наследственно конечных надстройках, в сб.: "Обобщенная вычислимость и определимость" (Вычислительные системы, 161), Новосибирск, Ин-т матем. СО РАН, 1998, 3 14.

19. А.Н. Хисамиев, Е-нумерация и Е-определимость в HF.M, в сб- " Структурные алгоритмические свойства вычислимости" (Вычислительные системы, 156), Новосибирск, Ин-т матем. СО РАН, 1996, 44 58.

20. Н.Г. Хисамиев, О сильно конструктивизируемых моделях разрешимой теории, Изв. Акад. наук Каз. ССР, сер. физ.-матем., №1, 1974, 83 -84.

21. J. Barwise, Admissible sets and structures, Berlin, Springer-Verlag, 1975.

22. J. Barwise, Admissible sets over Models of Set Theory, Generalized Recursion Theory, Amsterdam, North-Holland, 1974, 97 122.

23. H. Friedmann, Algorithmic procedures, generalized Turing algorithms and elementary recursion theory, Logic Colloqium'69 (R.O. Gandy and C.E.M. Yates eds), North-Holland, 1971, 361 390.

24. L. Henkin, A generalization of the concept of w-consistency, J. Symbolic Logic, 19, 1954, 183 196.

25. L. Henkin, A generalization of the concept of ¿¿-completeness, J. Symbolic Logic, 22, 1957, 1 14.

26. S. Kripke, Transfinite recursion on admissible ordinals, I, II (abstracts), J. Symbolic Logic, 33, 1964, 161 -162.

27. A. Levy, A hierarchy of formulas in set theory, Memoir Amer. Math.Soc., 57, 1965.

28. Y. Moschovakis, Abstract first order coraputability 1, Trans. Amer. Math. Soc., 138 (April, 1969).

29. S. Orey, On ¿¿-consistency and related properties, J. Symbolic Logic, 21, 1956, 246 252.

30. R. Platek, Foundations of recursion theory, Doctoral Dissertation and Supplement, Stanford, CA: Stanford Univ., 1966.

31. J.R. Shoenfield, Recursion theory, Lecture Notes in Logic, №1, Berlin, Springer-Verlag, 1993.

32. R.I. Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Berlin, Heidelberg, New York, London, Paris, Tokyo, Springer Verlag, 1987.РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ.

33. Пузаренко В.Г., О вычислимости над моделями разрешимых теорий, Алгебра и логика, 39, №2(2000), 170 197.

34. Пузаренко В.Г., Обобщенные нумерации и теорема Фридберга, в сб.: "Структурные и сложностные проблемы вычислимости" (Вычислительные системы, 165), Новосибирск, Ин-т матем. СО РАН, 1999, 153 176.

35. Puzarenko V.G., On computability over models of decidable theories, Algebra and models theory 2, Novosibirsk, Novosibirsk State Technical University, 1999, 94 103.

36. Пузаренко В.Г., О теории моделей на наследственно конечных надстройках, препринт №52, Новосибирск, ИДМИ НГУ, 2000.