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.
Original language | English |
---|---|
Pages (from-to) | 281-287 |
Number of pages | 7 |
Journal | Siberian Mathematical Journal |
Volume | 58 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Mar 2017 |
Keywords
- existential interpretability of structures
- weakly bounded Turing reducibility