RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 2009, том 50, номер 2, страницы 334–343 (Mi smj1962)

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

Равномерность сводимостей проблем представимости алгебраических систем

И. Ш. Калимуллин

Казанский гос. университет, механико-математический факультет, кафедра алгебры и математической логики, г. Казань

Аннотация: Найдены достаточные условия для того, чтобы для счетной алгебраической системы $\mathfrak B$, не имеющей степени, существовала счетная система $\mathfrak A$ со следующими свойствами: 1) для каждой изоморфной копии системы $\mathfrak B$ существует сводящаяся к ней по Тьюрингу изоморфная копия системы $\mathfrak A$; 2) не существует равномерной эффективной процедуры порождения копии системы $\mathfrak A$ по заданной копии системы $\mathfrak B$, даже обогащенной произвольным конечным набором констант.

Ключевые слова: вычислимость алгебраической структуры, тьюрингова степень, массовая проблема.

УДК: 510.53

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


 Англоязычная версия: Siberian Mathematical Journal, 2009, 50:2, 265–271

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


© МИАН, 2024