Батыршин И. И.
Q-сводимость и m-сводимость на вычислимо перечислимых множествах

Исследуются различия Q-сводимости и m-сводимости на вычислимо перечислимых множествах. Строится такое не вычислимое не m-полное вычислимо перечислимое множество B, что для всех вычислимо перечислимых множеств A ≤ _Q B выполняется A ≤ _m B. Доказывается, что для любого не вычислимого вычислимо перечислимого множества A существует такое вычислимо перечислимое множество B, что
A ≤ _Q B, но A _m B. Доказывается, что для любого простого множества B существует такое вычислимо перечислимое множество A, что A ≤ _Q B, но A _m B. Из последнего результата, в частности, следует, что в
Q-степени любого простого множества содержится бесконечно много в. п. m-степеней.

Batyrshin I. I.
Q-reducibility and m-reducibility on computably enumerable sets

We study the distinctions between Q-reducibility and m-reducibility on computably enumerable sets. We construct a noncomputable m-incomplete computably enumerable set B such that all computably enumerable sets A ≤ _Q B satisfy A ≤ _m B. We prove that for every noncomputable computably enumerable set A there exists a computably enumerable set B such that A ≤ _Q B but A _m B. We prove that for every simple set B there exists a computably enumerable set A such that A ≤ _Q B but A _m B. The last result implies in particular that the Q-degree of every simple set contains infinitely many computably enumerable m-degrees.

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

• PDF file
• PostScript file