Название статьи:
Полурешетки Роджерса классов бесконечных вычислимых множеств
Авторы: Иванов Ф.И., доктор физико-математических наук, профессор, кафедра налогов и таможенного дела, Байкальский государственный университет, 664003, г. Иркутск, ул. Ленина, 11,
IvanovFI@bgu.ru,
Корольков Ю.Д., доктор физико-математических наук, профессор, кафедра налогов и таможенного дела, Байкальский государственный университет, 664003, г. Иркутск, ул. Ленина, 11,
KorolkovUD@bgu.ru Для цитирования:
Иванов Ф. И. Полурешетки Роджерса классов бесконечных вычислимых множеств / Ф. И. Иванов, Ю. Д. Корольков // Известия Байкальского государственного университета. — 2017. — Т. 27, № 4. — С. 585–593. — DOI: 10.17150/2500-2759.2017.27(4).585-593.
В рубрике:
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ, СИСТЕМНЫЙ АНАЛИЗ
Год: 2017 Том: 27 Номер журнала: 4
Страницы: 585-593
Тип статьи: Научная статья
УДК: 510.57
DOI: 10.17150/2500-2759.2017.27(4).585-593
Аннотация:
В настоящее время полурешетки Роджерса являются одним из основных инструментов для моделирования сложности вычислимых объектов в теории вычислимости. Их применяют не только в классической теории, но и в отношении объектов, определяемых в иерархиях Клини - Мостовского или Ершова. В статье рассматриваются полурешетки Роджерса, полученные на основе монотонных вычислимых нумераций классов бесконечных вычислимых множеств. Результаты исследования относятся к базовой теории, заложенной трудами А. Н. Колмогорова, А. И. Мальцева и Ю. Л. Ершова. Вводятся понятия монотонной нумерации и монотонного идеала полурешетки Роджерса, показывается, что для задач оценки сложности на выделенных классах объектов ограничения монотонными структурами не приводят к существенному уменьшению качества оценок. В работе доказываются теоремы об изоморфизме и эпиморфизмах монотонных идеалов полурешеток Роджерса для широкого спектра классов бесконечных вычислимых множеств. В качестве следствий этих теорем получены структурные оценки полурешеток Роджерса, аналогичные стандартным оценкам в литературе.
Ключевые слова: Полурешетки Роджерса, теория вычислимости, вычислимые множества, вычислимые нумерации, морфизмы
Информация о статье: Дата поступления 15 июня 2017 г. Дата принятия к печати 20 ноября 2017 г. Дата онлайн-размещения 27 ноября 2017 г.
Список цитируемой литературы: - Колмогоров А. Н. К определению алгоритма / А. Н. Колмогоров, В. А. Успенский // Успехи математических наук. - 1958. - Т. 13, № 4 (82). - С. 3-28.
- Ершов Ю. Л. Нумерации семейств общерекурсивных функций / Ю. Л. Ершов // Сибирский математический журнал. - 1967. - Т. 8, № 5. - С. 1015-1025.
- Ершов Ю. Л. Теория нумераций / Ю. Л. Ершов. - М. : Наука, 1977. - 416 с.
- Марченков С. С. О вычислимых нумерациях семейств общерекурсивных функций / С. С. Марченков // Алгебра и логика. - 1972. - Т. 11, № 5. - С. 588-607.
- Гончаров С. С. Однозначные вычислимые нумерации / С. С Гончаров // Алгебра и логика. - 1980. - Т. 19, № 1. - С. 23-44.
- Бадаев С. А. О полурешетках Роджерса семейств арифметических множеств / С. А. Бадаев, С. С. Гончаров // Алгебра и логика. - 2001. - Т. 40, № 5. - С. 507-522.
- Kummer M. Numberings of R1 ? F/ M. Kummer // Computer Science Logic 1988 / ed. by E. Borger, H. Kleine, M. M. Richter // Lecture Notes in Computer Science 385. - Berlin : Springer Verlag, 1989. - P. 166-186.
- Kummer M. Some applications of computable one-one numberings / M. Kummer // Archive for Mathematical Logic. - 1990. - Vol. 30, № 4. - P. 219-230.
- Гончаров С. С. Обобщенно вычислимые нумерации и нетривиальные полурешетки Роджерса / С. С. Гончаров, А. Сорби // Алгебра и логика. - 1997. - Т. 36, № 6. - С. 621-641.
- Подзоров С. Ю. Начальные сегменты в полурешетках Роджерса 0 n ? -вычислимых нумераций / С. Ю. Подзоров // Алгебра и логика. - 2003. - Т. 42, № 2. - С. 211-226.
- Корольков Ю. Д. Алгоритмические свойства вычислимых нумераций / Ю. Д. Корольков, С. С. Оспичев. - Иркутск : Изд-во ИГУ, 2013. - 106 с.
- Роджерс X. Теория рекурсивных функций и эффективная вычислимость / X. Роджерс. - М. : Мир, 1972. - 624 с.
- Friedberg R. M. Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication / R. M. Friedberg // Journal of Symbolic Logic. - 1958. - Vol. 23. - P. 309-316.
- Pour-El M. B. Recursively enumerable classes and their applications to sequences of formal theories / M. B. Pour-El, H. Putnam // Archiv fur Mathematische. Logik und Grundlagenforschung. - 1965. - Vol. 8. - P. 104-121.
- Мальцев А. И. Алгоритмы и рекурсивные функции / А. И. Мальцев. - М. : Наука, 1965. - 392 с.
- Корольков Ю. Д. Дискретные модели: представление конечными деревьями и разрешимость формальных теорий / Ю. Д. Корольков, В. И. Мартьянов. - Иркутск : Изд-во ИРНИТУ, 2017. - 160 с.