Баженов Н. А., Марчук М. И.
Степени автоустойчивости относительно сильных конструктивизаций графов

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

N. A. Bazhenov, M. I. Marchuk
Degrees of Autostability Relative to Strong Constructivizations of Graphs

We show that each computably enumerable Turing degree is a degree of autostability relative to strong constructivizations for a decidable directed graph. We construct a decidable undirected graph whose autostability spectrum relative to strong constructivizations is equal to the set of all PA-degrees.

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

Свободный доступ к полным текстам предоставляется после 1 июля года, следующего за годом публикации