И. Ш. Калимуллин, В. Л. Селиванов, А. Н. Фролов, “Спектры степеней структур”, Итоги науки и техн. Соврем. мат. и ее прил. Темат. обз., 2018, том 158,страницы 23

Эта публикация цитируется в 2 статьях

Спектры степеней структур

И. Ш. Калимуллин^a, В. Л. Селиванов^ba, А. Н. Фролов^a

^a Казанский (Приволжский) федеральный университет
^b Институт систем информатики им. А. П. Ершова СО РАН, г. Новосибирск

Аннотация: В обзоре обсуждаются спектры вычислимости счетных структур, дающие естественную меру сложности невычислимых структур. Понятие спектра структуры является основным инструментом исследования алгоритмических свойств счетных структур. Наряду с обзором имеющихся результатов приведем доказательства нескольких новых результатов, иллюстрирующих вариант метода интерпретаций, являющийся основным методом данного направления. Обсуждаются некоторые открытые вопросы.

Ключевые слова: структура, вычислимая структура, спектр структуры, интерпретация.

УДК: 510.5, 512.565.2

MSC: 03D45, 03C57