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

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

Goncharov S. S., Bazhenov N. A., Marchuk M. I.
The index set of Boolean algebras autostable relative to strong constructivizations

We obtain exact estimates for the algorithmic complexity for the classes of strongly constructivizable computable models autostable relative to strong constructivizations and belonging to the following natural classes: Boolean algebras, distributive lattices, rings, commutative semigroups, and partial orders.

DOI 10.17377/smzh.2015.56.303

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

Полный текст статьи / Full texts:

• PDF file
• PostScript file