Аннотация:
Приводится оценка алгоритмической сложности класса вычислимых структур с двумя отношениями эквивалентности, имеющих сильную конструктивизацию и автоустойчивых относительно сильных конструктивизаций. Строятся кодирования линейного порядка и автоморфно нетривиального ориентированного иррефлексивного графа в структуру с двумя отношениями эквивалентности. Доказывается, что такие кодирования сохраняют спектр степеней и $d$-вычислимую размерность.
Ключевые слова:автоустойчивость относительно сильных конструктивизаций, вычислимая модель, гиперарифметическая иерархия, индексное множество, иррефлексивный ориентированный граф, кодирование, линейный порядок, сильно конструктивизируемая модель, структура с двумя отношениями эквивалентности.
Полный текст:
PDF файл (174 kB)
