On some reducibility and existential interpretability of structures

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)281-287
Number of pages7
JournalSiberian Mathematical Journal
Volume58
Issue number2
DOIs
Publication statusPublished - 1 Mar 2017

Keywords

  • existential interpretability of structures
  • weakly bounded Turing reducibility

Fingerprint

Dive into the research topics of 'On some reducibility and existential interpretability of structures'. Together they form a unique fingerprint.

Cite this