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

• Пузаренко, Вадим Григорьевич
• кандидат физико-математических наук
• 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

Введение диссертации (часть автореферата) на тему «Об алгоритмических и структурных свойствах вычислимости над моделями»

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

Ю.Л. Ершов

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

Первые результаты в области вычислимости появились еще задолго до появления строгого математического понятия алгоритма. С глубокой древности до нас дошли известные многим со школьной скамьи алгоритм Евклида, "решето" Эратосфена, алгоритмы нахождения приближений трансцендентных чисел 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.

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

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

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

Решение проблемы 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.

Утверждения из главы 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 посвящена изучению теоретико-модельных свойств наследственно конечных надстроек над моделями не более, чем счетных сигнатур. Было замечено, что резольвентные наследственно конечные множества в сигнатурном обогащении, в котором резольвента определяется без параметров, единственны с точностью до изоморфизма в своей теории.

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

Ответ на вопрос, как следует из примеров главы 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, а также всем участникам семинаров "Алгебра и логика" и "Теория нумераций". Особая признательность молодым сотрудникам и аспирантам кафедры алгебры и математической логики Новосибирского Государственного Университета за помощь на завершающем этапе оформления текста диссертации.

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

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

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

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

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.