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

• Автор: Пузаренко, Вадим Григорьевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Новосибирск
• Количество страниц: 105 с.

ВВЕДЕНИЕ.
В теории допустимых множеств вопросы, ставить легко; искать ответы на них значительно сложнее.
Ю.Л. Ершов
Обобщенная вычислимость — новое направление математической логики, зародившееся на стыке теории вычислимости, теории моделей и теоретического программирования в работах Я. Московакиса [30] и X. Фридмана [24].
Первые результаты в области вычислимости появились еще задолго до появления строгого математического понятия алгоритма. С глубокой древности до нас дошли известные многим со школьной скамьи алгоритм Евклида, “решето” Эратосфена, алгоритмы нахождения приближений трансцендентных чисел п и е, метод Штурма и т. д. Одним из фундаментальных вкладов математической логики в развитие математики и науки в целом стала формализация вычислимых функций и изучение их алгоритмических свойств. Эта программа получила огромный толчок в 1931 году в связи с известной теоремой Гёделя о неполноте, использующей понятие примитивно рекурсивной функции, и привела к появлению в течение первой половины 1930-х годов ряда определений вычислимых функций: по Чёрчу, Гёделю, Клини, Посту и Тьюрингу. Вскоре было доказано, что все эти определения задают один и тот же класс математических функций, который, как принято считать (согласно тезису Чёрча), состоит в точности из “эффективно вычислимых” функций. Неформально, эти функции можно вычислить с помощью современного компьютера, игнорирующего ограничения на время вычислений и используемую память. С данным понятием тесно связано понятие перечислимого подмножества множества натуральных чисел, а именно, множества, которое может быть порождено вычислимой процедурой [34].
Кроме вышеупомянутых, выделим подход Шёнфилда [33], [13], использующий абстрактные вычислительные устройства с программами,
написанными на языке, близким и по духу, и по содержанию к языку АССЕМБЛЕР, а также подход Е-программирования (или семантического программирования), разработанный С.С. Гончаровым, Ю.Л. Ершовым и Д.И. Свириденко [3]. “Устройством” в семантическом программировании, в отличие от остальных формализаций, в основе которых лежат алгоритмы и абстрактные вычислительные машины, служит семантика, а роль программ выполняют формулы специального вида — Е-формулы, — что позволяет определить вычислимость над абстрактной структурой ЯЯ как Е-определимость в допустимых множествах над Ш. Эта идея была предложена Ю.Л. Ершовым в 1983 году [7] и нашла свое отражение в работах A.C. Морозова [29], В.А. Руднева [15], [16], М.В. Коровиной [10], О.В. Кудинова [11], А.Н. Хисамиева [20]. В связи с этим стоит упомянуть книгу Ю.Л. Ершова “Определимость и вычислимость” [4], [5], выдержавшую два издания и ставшую фудаментальной в данной области.
Примером еще одного подхода к обобщенной вычислимости служит формализация, предложенная омскими учеными И.В. Ашаевым, В.Я. Беляевым и А.Г. Мясниковым [1], использующая понятие некоторого абстрактного вычислительного устройства (В55'-машины), заданного на наследственно конечной списочной надстройке над абстрактной структурой. Следуя работе [3], можно определить вычислимость над моделью 9Л как Е-определимость в наследственно конечной списочной надстройке над Ш. Отметим, что наследственно конечная списочная надстройка вычислимо эквивалентна наследственно конечной надстройке — наименьшей по включению модели теории KPU.
Аксиомы теории KP (происходит от начапьных букв фамилий основателей Kripke, Platek) были введены в 1966 году Платеком [32]. Он определил допустимое множество как транзитивное, непустое множество, замкнутое относительно операции ТС и удовлетворяющее До-выделению и Е-рефлексии. В 1964 году Крипке независимо ввел аналогичное понятие, заменив Е-рефлексию Е-замещением [27]. Завершающий вид теория допустимых множеств приобрела в работах Дж. Барвайса [23], [22],

предложившего рассматривать допустимые множества с праэлементами (буква U в сокращении KPU — это начальная буква слова Urelement). Понятия До- и Ei-формул, служащие фундаментом этой теории, были введены Леви в 1965 году [28].
С основания в начале 60-х годов, теория допустимых множеств становится основой взаимодействия между теорией модели, теорией вычислимости и теорией множеств. Перечисленные теории имеют дело, в частности, с проблемами определимости и существования множеств.
В теории допустимых множеств основное внимание уделяется изучению свойств Е-подмножеств — подмножеств, определимых Е-формула-ми, — в отличие от классической вычислимости, где перечислимые множества и вычислимые функции являются взаимозаменяемыми. Для наследственно конечных надстроек имеется единое представление Е-под-множеств в терминах классической вычислимости.
ТЕОРЕМА 2.1.1 (вариант теоремы Вайценавичюса [2]).
Пусть HF(®T) — наследственно конечная надстройка над произвольной моделью ЯЛ. Если подмножество А С HF(M) определимо некоторой И-формулой Ф(ю), то существует вычислимая последовательность Аф = {Аф}пеш множеств, состоящих из геделевых номеров 3-формул, для которой выполняются соотношения <т(Дф) С <т_(Ф) и
А = {Term(n,.g)|3

[7а]))}. (1)
Выполняется и обратное: если для множества А существует вычислимая последовательность А = {An}ng„ такая, что <т(А) конечно и множество А представимо в виде (1), то оно определимо некоторой Yi-формулой Фд, для которой с(Фд) С а+(А).
К тому же, существует эффективная процедура нахождения по Л-формуле Ф (вычислимой последовательности А) вычислимой последовательности Аф (-формулы Фд).
В условии теоремы через сг+(А) обозначается множество сигнатурных символов, встречающихся в формулах из UА, в совокупности с сигна-
термов 5о, 1 ЗА;-1, Зр, ... , э1к_1 сигнатуры сг, то
ф0_ф1 _ у (Д (* = в;(<))),
7гб5п *<Да
если /г > 0; и Ф° т0, Ф1 *=? "Ух, если к = 0;
гг) в остальных случаях полагаем Ф° Тх, Ф1 ”'т0;
- если Ф = (го £ Гх), где г0, Гх — термы сигнатуры а', то будем различать несколько случаев:
г) если гх = 0 или Гх — терм сигнатуры сг, то Ф° тх, Ф1 ±=г Уо; н) если г0 = „(«0) )Г1 = {„(3о' > -ч)} Для некоторых п £ ш и термов 5о, , «*-1, «о, > 5х,_х сигнатуры сг, то
ф° - ф1 V (Д(* = <«))’
тгБп г<к
если к > 0; и Ф° т0, Ф1 с=г "Ух, если & = 0;
ш) если г0 = *„0Оо

(*о С 0(г0)... ,г*о_х)) У(*0 £ *т1(«о
ю) в остальных случаях полагаем Ф° с=г Гх, Ф1 “Уо;
- если Ф имеет вид, который не был рассмотрен выше, то полагаем Ф° п, Ф1 с=г "то.
В силу конструкции справедливо следующее: любая Д0-формула сигнатуры су' от прапеременных эквивалентна некоторой конечной бескванторной формуле сигнатуры сг.
§5. НЕ-ЛОГИКА КАК ЧАСТНЫЙ СЛУЧАЙ ОУЛОЕИКИ.
Этот параграф посвящен описанию методов построения наследствен-