|
This article is cited in 1 scientific paper (total in 1 paper)
On some reducibility and existential interpretability of structures
A. S. Morozovab a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
Abstract:
We prove the embeddability of the structure of Turing degrees into the structure of degrees of existential interpretability. The notion of weakly bounded Turing reducibility ($\operatorname{wbT}$-reducibility) arises in the proof naturally. We demonstrate that this reducibility is situated strictly between the bounded truth-table reducibility and Turing reducibility and differs from the truth-table reducibility.
Keywords:
existential interpretability of structures, weakly bounded Turing reducibility.
Received: 05.05.2016
Citation:
A. S. Morozov, “On some reducibility and existential interpretability of structures”, Sibirsk. Mat. Zh., 58:2 (2017), 365–374; Siberian Math. J., 58:2 (2017), 281–287
Linking options:
https://www.mathnet.ru/eng/smj2865 https://www.mathnet.ru/eng/smj/v58/i2/p365
|
|