On some reducibility and existential interpretability of structures Full article
| Journal |
Siberian Mathematical Journal
ISSN: 0037-4466 , E-ISSN: 1573-9260 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2017, Volume: 58, Number: 2, Pages: 281-287 Pages count : 7 DOI: 10.1134/S0037446617020100 | ||||
| Tags | existential interpretability of structures; weakly bounded Turing reducibility | ||||
| Authors |
|
||||
| Affiliations |
|
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 (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. © 2017, Pleiades Publishing, Ltd.
Cite:
Morozov A.S.
On some reducibility and existential interpretability of structures
Siberian Mathematical Journal. 2017. V.58. N2. P.281-287. DOI: 10.1134/S0037446617020100 WOS Scopus OpenAlex
On some reducibility and existential interpretability of structures
Siberian Mathematical Journal. 2017. V.58. N2. P.281-287. DOI: 10.1134/S0037446617020100 WOS Scopus OpenAlex
Original:
Морозов А.С.
Об одной сводимости и экзистенциальной интерпретируемости cтруктур
Сибирский математический журнал. 2017. Т.58. №2. С.365-374. DOI: 10.17377/smzh.2017.58.210 РИНЦ MathNet
Об одной сводимости и экзистенциальной интерпретируемости cтруктур
Сибирский математический журнал. 2017. Т.58. №2. С.365-374. DOI: 10.17377/smzh.2017.58.210 РИНЦ MathNet
Identifiers:
| Web of science: | WOS:000400087100010 |
| Scopus: | 2-s2.0-85018854178 |
| OpenAlex: | W2608739822 |