Аннотация
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.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 281-287 |
Число страниц | 7 |
Журнал | Siberian Mathematical Journal |
Том | 58 |
Номер выпуска | 2 |
DOI | |
Состояние | Опубликовано - 1 мар 2017 |