Введение к работе
Актуальность темы. Упар - достаточно гибкое, универсальное пони тис и поэтому является объектом исследований енецналис гон разных разделом математики. 13 частііости,ішчисли'іх;льііьіе возможное гп ушірон интересовали, начиная с классиков оспой мин'мапімі Дедекинда и Гильберта, многих специалистов в области математической логики и теории алгоритмом. В предлагаемой работе вводит-ся понятие характрисгики упара, с помощью которой получен ряд результатов, дополняющих, обобщающих, а иногда, и уточняющих некоторые известные результаты. Тик, и глаие I обобщена теорема о гомоморфизме1 (теоремаі.2.2); сущестпопание операций сложения и умножения к произвольном упаре, и отличие от доказательства Кальмара2 , установлено без апеллирования к актуально бесконечному натуральному ряду.
Н глаие 11 установлен бесконечный класс у нарой, и которых определена функция xv, чем уточняется соответствующий ре'іулі. чат Гильберта. Методы, развитые в глаие II, позволяют запершить решении одной проблемы Гжеторчики "', типично решенной Ргцнп том 4.
' 1,еоп llelkin. On mathematical induction. The American Mathematical Monthly, V.67, N4, April,1960 (n русском переводе Л.Гсикіш. О математической индукции. Гос. издание фи.'і мат.ли гера туры, Моек ' ма, 1062).
2 Acta .Sei.Mntli.(.4zeged) V.O.N'1,10-10, p.227-2:i2.
*' Grzegorczyk A. Some classes of recursive functions, Rozprawy Ma-teiiiaticzne, IV, VVaiH/awa, 1953. (в русском переводе А.Гжегорчик. Некоторые классы рекурсивных функций, в сборнике Проблемы математической логики, Мир, Москва, 1970, стр.9-49.)
'' Hodding П. Uher ilie Kliminierkeit von ПеГіпіІіоинеІіеніаІа in «Ііч-Theirie der rectirsiven lMjnctioneri, Z.inath.Logik und Grunlag. iler Math., 10, N4, 1904, p. 315-330.
В главе III введены некоторые новые арифметические теории, М-прифмктики, входящие в противоречие с классической арифметикой ІІеано. В работе обосновывается целесообразность рассмотрения этих альтернативных арифметик: они непротиворечивы (как известно, непротиворечивость арифметики Пеано недоказуема.) и являются источником новых представлений о классе аффективно вычислимых Функций. 11 отличие от обычной формальной арифметики, лежащей и основе теории рекурсии, которая позволяет строить модели вычислимости лишь в предположении о бесконечности натурального ряда, подход, основанный на унарах конечной характеристики, позволяет строить модели и изучать свойства реальной вычислимости.
Целью работы является изучение вазможностей задания арифметических функций рекурсивными средствами без априорных .предположений о свойствах модели реализации, а также исследование связи между понятиями представимости функции в некоторой /-/-арифметике и ее представимости на стандартных моделях этой арифметики. Основная цель диссертации - исследование унароп в следующих двух аспектах;
-
Изучение унароп (в связи с тем, что они являются носителями свойства индукции) с точки зрения возможности реализации на них рекурсивных схем.
-
Изучение уиарои, как конечных моделей некоторых формальных теорий первого порядка.
Методы исследования. В работе, в основном, применены традиционные, частично модифицированные, методы теории рекурсивных функций, теории модели и теории чисел.
Научная новизна и теоретическая цепкость. В работе:
-
введеііо понятие характеристики унара, которое позволяет полноценно исследовать механизм построений но индукции;
-
установлены критерии представимости арифметических
функций на конкретном унаре и на всех уаарах;
3) введен универсальный способ задания целозначпых функций, а именно, через разложение и ряд Полин15. Понятие ряда Полип вводится нами впервые исходя из задач о целоэиачных полиномах которые можно продолжить до бесконечного ряда и виде конечных линейных комбинаций биномиальных коэффициентов;
'1) установлен клпес псех /Ш-функций, продстапимых iia всех унарах;
б) решением одной из проблем Гжегорчика продемонстрирован новый метод решении задач теории рекурсивной функции;
G) введен ряд новых формальных теорий (М-арифметики), допускающих конечные модели.
Апробация работы. Результаты диссертации докладывались в ВЦ ЛИ Армении (1972,1994), на Всесоюзной конференции по теории грифов (Одесса, 1973), на семинарах кафедры мачиматической логики МГУ (Москва, 1978, 1981, 1985), на I и II Республиканских научных конференциях преподавателей вузов Армении (1983, 1085), на VIII Всесоюзной конференции по математической логике (Моск-ва,198(і), па семинара по теории нумерации ИГУ (Новосибирск, 1983), на семинаре ф-та прикладной математики ЛГУ (Ленинград, 1990) и на семинарах кафедры высшей геометрии и алгебры ЮГУ.
// у б л и к а ц и и. Основные результаты диссертации опубликованы в13 статьях.
Структура и объем диссертации. Диссертация изложена на 78 страницах машинописного текста, состоит из введения и трех глав. Библиография содержит 37 ипнмопопнний.