|
Sibirskii Matematicheskii Zhurnal, 2009, Volume 50, Number 2, Pages 334–343
(Mi smj1962)
|
|
|
|
This article is cited in 3 scientific papers (total 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.
Received: 28.05.2008
Citation:
I. Sh. Kalimullin, “Uniform reducibility of representability problems for algebraic structures”, Sibirsk. Mat. Zh., 50:2 (2009), 334–343; Siberian Math. J., 50:2 (2009), 265–271
Linking options:
https://www.mathnet.ru/eng/smj1962 https://www.mathnet.ru/eng/smj/v50/i2/p334
|
Statistics & downloads: |
Abstract page: | 294 | Full-text PDF : | 83 | References: | 50 | First page: | 1 |
|