Морозов А. С.
Об одной сводимости и экзистенциальной интерпретируемости структур

Доказывается вложимость структуры тьюринговых степеней в структуру степеней по экзистенциальной интерпретируемости. В доказательстве естественным образом возникает понятие слабо ограниченной тьюринговой сводимости ($\operatorname{wbT}$-сводимости). Доказывается, что эта сводимость расположена строго между ограниченной табличной и тьюринговой сводимостями, а также отличается от табличной сводимости.

A. S. Morozov
On some reducibility and existential interpretability of structures

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.

DOI 10.17377/smzh.2017.58.210
Ключевые слова: экзистенциальная интерпретируемость структур, слабо ограниченная тьюрингова сводимость.

Полный текст статьи / Full texts:

• PDF file
• PostScript file