Н. А. Баженов, М. И. Марчук, “Степени автоустойчивости относительно сильных конструктивизаций графов”, Сиб. матем. журн., 2018, том 59, номер 4,страницы 719

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

Степени автоустойчивости относительно сильных конструктивизаций графов

Н. А. Баженов^ab, М. И. Марчук^ab

^a Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090
^b Новосибирский гос. университет, ул. Пирогова, 1, Новосибирск 630090

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

Ключевые слова: вычислимая модель, сильно конструктивизируемая модель, автоустойчивость, автоустойчивость относительно сильных конструктивизаций, степень автоустойчивости относительно сильных конструктивизаций, спектр автоустойчивости относительно сильных конструктивизаций, PA-степень, вычислимо перечислимая степень, граф.

УДК: 510.5

MSC: 35R30

Статья поступила: 01.11.2017

DOI: 10.17377/smzh.2018.59.401