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 (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

Fingerprint Подробные сведения о темах исследования «On some reducibility and existential interpretability of structures». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать