RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1995, том 34, номер 6, страницы 667–680 (Mi al2332)

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

Рекурсивно несовместные алгоритмические проблемы на $1$-конструктивизируемых дистрибутивных решетках с относительными дополнениями

С. Т. Федоряев

Институт математики Сибирского отделения Российской академии наук, г. Новосибирск

Аннотация: Для произвольной $1$-конструктивизируемой дистрибутивной решетки $\mathfrak{A}$ с относительными дополнениями и бесконечным множеством атомов строится вычислимое семейство $\Omega$ алгоритмических $\sigma_2^r$-проблем на $\mathfrak{A}$, каждая из которых разрешима при подходящей конструктивизаций решетки $\mathfrak{A}$, но при любой конструктивизации произвольные две алгоритмические проблемы из $\Omega$ не могут быть одновременно разрешимы. Тем самым для $1$-конструктивизируемых дистрибутивных решеток с относительными дополнениями получается решение проблем спектра и соотношений алгоритмических размерностей и находятся критерии существования наименьшего элемента в структуре алгебраической сводимости и алгебраические условия решения задачи эффективного выбора конструктивизаций по спецификациям проблем.

УДК: 510.53:510.67

Поступило: 29.06.1994


 Англоязычная версия: DOI: 10.1007/BF00739333

Реферативные базы данных:


© МИАН, 2024