RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2009 Volume 50, Number 2, Pages 334–343 (Mi smj1962)

This article is cited in 3 papers

Uniform reducibility of representability problems for algebraic structures

I. Sh. Kalimullin

Kazan State University, Faculty of Mechanics and Mathematics, Kazan

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

Keywords: computability of an algebraic structure, Turing degree, mass problem.

UDC: 510.53

Received: 28.05.2008


 English version:
Siberian Mathematical Journal, 2009, 50:2, 265–271

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024