|
Сибирский математический журнал, 2009, том 50, номер 2, страницы 334–343
(Mi smj1962)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Равномерность сводимостей проблем представимости алгебраических систем
И. Ш. Калимуллин Казанский гос. университет, механико-математический факультет, кафедра алгебры и математической логики, г. Казань
Аннотация:
Найдены достаточные условия для того, чтобы для счетной алгебраической системы $\mathfrak B$, не имеющей степени, существовала счетная система $\mathfrak A$ со следующими свойствами: 1) для каждой изоморфной копии системы $\mathfrak B$ существует сводящаяся к ней по Тьюрингу изоморфная копия системы $\mathfrak A$; 2) не существует равномерной эффективной процедуры порождения копии системы $\mathfrak A$ по заданной копии системы $\mathfrak B$, даже обогащенной произвольным конечным набором констант.
Ключевые слова:
вычислимость алгебраической структуры, тьюрингова степень, массовая проблема.
Статья поступила: 28.05.2008
Образец цитирования:
И. Ш. Калимуллин, “Равномерность сводимостей проблем представимости алгебраических систем”, Сиб. матем. журн., 50:2 (2009), 334–343; Siberian Math. J., 50:2 (2009), 265–271
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj1962 https://www.mathnet.ru/rus/smj/v50/i2/p334
|
|