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

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

Kalimullin  I. Sh.
Uniform reducibility of representability problems for algebraic structures

Given a countable algebraic structure with no degree we find sufficient conditions for the existence of a countable structure with the following properties: (1) for every isomorphic copy of there is an isomorphic copy of Turing reducible to the former; (2) there is no uniform effective procedure for generating a copy of given a copy of even having been enriched with an arbitrary finite tuple of constants.

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

• PDF file (435 KB)
• PostScript file (815 KB)