Аннотация:
В обзоре обсуждаются спектры вычислимости счетных структур, дающие естественную меру сложности невычислимых структур. Понятие спектра структуры является основным инструментом исследования алгоритмических свойств счетных структур. Наряду с обзором имеющихся результатов приведем доказательства нескольких новых результатов, иллюстрирующих вариант метода интерпретаций, являющийся основным методом данного направления. Обсуждаются некоторые открытые вопросы.
Работа И. Ш. Калимуллина выполнена при поддержке Министерства образования и науки РФ в рамках субсидий, выделенных Казанскому федеральному университету для выполнения государственного задания в сфере научной деятельности (проект № 1.1515.2017/4.6) и проекта Министерства образования и науки РФ «федеральный профессор математики» № 1.451.2016/1.4. Работа В. Л. Селиванова выполнена при поддержке Российского научного фонда (проект № 18-11-00028). Работа А. Н. Фролова выполнена при поддержке Российского фонда фундаментальных исследований (проект № 16-31-60077).
Образец цитирования:
И. Ш. Калимуллин, В. Л. Селиванов, А. Н. Фролов, “Спектры степеней структур”, Труды семинара кафедры алгебры и математической логики Казанского (Приволжского) федерального университета, Итоги науки и техн. Соврем. мат. и ее прил. Темат. обз., 158, ВИНИТИ РАН, М., 2018, 23–39; J. Math. Sci. (N. Y.), 256:2 (2021), 143–159
\RBibitem{KalSelFro18}
\by И.~Ш.~Калимуллин, В.~Л.~Селиванов, А.~Н.~Фролов
\paper Спектры степеней структур
\inbook Труды семинара кафедры алгебры и математической логики Казанского (Приволжского) федерального университета
\serial Итоги науки и техн. Соврем. мат. и ее прил. Темат. обз.
\yr 2018
\vol 158
\pages 23--39
\publ ВИНИТИ РАН
\publaddr М.
\mathnet{http://mi.mathnet.ru/into411}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3940092}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2021
\vol 256
\issue 2
\pages 143--159
\crossref{https://doi.org/10.1007/s10958-021-05424-0}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/into411
https://www.mathnet.ru/rus/into/v158/p23
Эта публикация цитируется в следующих 2 статьяx:
Nikolay Bazhenov, “Computable Heyting Algebras with Distinguished Atoms and Coatoms”, J of Log Lang and Inf, 32:1 (2023), 3
М. В. Зубков, А. Н. Фролов, “Спектральная универсальность линейных порядков с одним бинарным отношением”, Сиб. матем. журн., 61:3 (2020), 587–593; M. V. Zubkov, A. N. Frolov, “Spectral universality of linear orders with one binary relation”, Siberian Math. J., 61:3 (2020), 463–467
Цитирование в формате AMSBIB
Обратная связь: