Аннотация:
Доказано, что вычислимый ординал $\alpha$ является автоустойчивым относительно сильных конструктивизаций в том и только том случае, когда $\alpha<\omega^{\omega+1}$. Получена точная оценка алгоритмической сложности для класса сильно конструктивизируемых линейных порядков, являющихся автоустойчивыми относительно сильных конструктивизаций.
Ключевые слова:
вычислимая модель, сильно конструктивизируемая модель, автоустойчивость, автоустойчивость относительно сильных конструктивизаций, линейный порядок, вычислимый ординал, индексное множество.
Исследования С.С. Гончарова выполнены при частичной финансовой поддержке РФФИ (проект 13-01-91001-АНФ-а). Исследования Н.А. Баженова частично поддержаны Советом по грантам
Президента РФ для государственной поддержки ведущих научных школ (проект НШ-860.2014.1).
Исследования М.И. Марчук частично поддержаны РФФИ (проект 14-01-00376).
Образец цитирования:
С. С. Гончаров, Н. А. Баженов, М. И. Марчук, “Индексное множество автоустойчивых относительно сильных конструктивизаций линейных порядков”, Вестн. НГУ. Сер. матем., мех., информ., 15:3 (2015), 51–60; J. Math. Sci., 221:6 (2017), 840–848
Н. А. Баженов, М. И. Марчук, “О спектрах разрешимой категоричности для почти простых моделей”, Алгебра и логика, 62:4 (2023), 441–457
Н. А. Баженов, “Спектры категоричности вычислимых структур”, Итоги науки и техн. Сер. Соврем. мат. и ее прил. Темат. обз., 157 (2018), 42–58; N. A. Bazhenov, “Categoricity spectra of computable structures”, J. Math. Sci. (N. Y.), 256:1 (2021), 34–50
Nikolay Bazhenov, Margarita Marchuk, Lecture Notes in Computer Science, 10936, Sailing Routes in the World of Computation, 2018, 40
С. С. Гончаров, Н. А. Баженов, М. И. Марчук, “Индексное множество автоустойчивых относительно сильных конструктивизаций групп”, Сиб. матем. журн., 58:1 (2017), 95–103; S. S. Goncharov, N. A. Bazhenov, M. I. Marchuk, “The index set of the groups autostable relative to strong constructivizations”, Siberian Math. J., 58:1 (2017), 72–77
М. И. Марчук, “Индексное множество автоустойчивых относительно сильных конструктивизаций структур с двумя отношениями эквивалентности”, Алгебра и логика, 55:4 (2016), 465–477; M. I. Marchuk, “Index set of structures with two equivalence relations that are autostable relative to strong constructivizations”, Algebra and Logic, 55:4 (2016), 306–314
Цитирование в формате AMSBIB
Обратная связь: