On some reducibility and existential interpretability of structures
- Авторлар: Morozov A.1
-
Мекемелер:
- Sobolev Institute of Mathematics
- Шығарылым: Том 58, № 2 (2017)
- Беттер: 281-287
- Бөлім: Article
- URL: https://journals.rcsi.science/0037-4466/article/view/171085
- DOI: https://doi.org/10.1134/S0037446617020100
- ID: 171085
Дәйексөз келтіру
Аннотация
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.
Авторлар туралы
A. Morozov
Sobolev Institute of Mathematics
Хат алмасуға жауапты Автор.
Email: morozov@math.nsc.ru
Ресей, Novosibirsk