|
СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ
АННОТАЦИИ
Морозов А. С. Об одной сводимости и экзистенциальной интерпретируемости структур //
Том 58 (2017), Номер 2,
стр. 365374
Доказывается вложимость структуры тьюринговых степеней в структуру степеней по экзистенциальной интерпретируемости. В доказательстве естественным образом возникает понятие слабо ограниченной тьюринговой сводимости ($\operatorname{wbT}$-сводимости). Доказывается, что эта сводимость расположена строго между ограниченной табличной и тьюринговой сводимостями, а также отличается от табличной сводимости.
|
|
© Сибирский Математический Журнал, 2003-2006
|
|