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

Sibirsk. Mat. Zh., 2017 Volume 58, Number 2, Pages 365–374 (Mi smj2865)

This article is cited 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.

UDC: 510.5

MSC: 35R30

Received: 05.05.2016

DOI: 10.17377/smzh.2017.58.210


 English version:
Siberian Mathematical Journal, 2017, 58:2, 281–287

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025