Preview

Моделирование и анализ информационных систем

Расширенный поиск

Степени перечислимости ограниченных множеств

https://doi.org/10.18255/1818-1015-2022-2-104-114

Полный текст:

Аннотация

Термин <<тотальная степень перечислимости>> связан с тем, что е-степень тотальна тогда и только тогда, когда она содержит график некоторой тотальной функции. В ряде работ автора и группы математиков из University of Wisconsin-Madison рассматривались так называемые <<граф-кототальные степени перечислимости>>, т.е. е-степени, содержащие дополнение графика некоторой тотальной функции $f(x)$. В данной статье сделан следующий шаг -- рассмотрены степени перечислимости множеств, ограниченных сверху или снизу графиком тотальной функции. Более точно, множество A ограничено сверху, если $A=\\{\\langle x,y\\rangle:y < f(x)\\}$ для некоторой тотальной функции f(x) и множество A ограничено снизу, если $A=\\{\\langle x,y\\rangle:y > f(x)\\}$ для некоторой тотальной функции $f(x)$. В статье приводится ряд результатов, показывающих существование нетотальных степеней перечислимости, содержащих ограниченные множества, причем построенные е-степени являются квазиминимальными. Важным является результат, утверждающий, что ограниченные множества обладают свойством Фридберга, связанным с~инверсией скачка.

Об авторе

Борис Яковлевич Солон
Ивановский государственный университет
Россия


Список литературы

1. U. Andrews, H. Ganchev, R. Kuyper, S. Lempp, J. Miller, A. Soskova, and M. Soskova, “On cototality and the skip operator in the enumeration degrees”, Transactions of the American Mathematical Society, vol. 372, no. 3, pp. 1631-1670, 2019.

2. B. Solon and S. Rozhkov, “Enumeration degrees of the bounded total sets”, in International Conference on Theory and Applications of Models of Computation, Springer, 2006, pp. 737-745.

3. S. Rozhkov, “Properties of e-degrees of the bounded total sets”, Automatic Control and Computer Sciences, vol. 44, no. 7, pp. 452-454, 2010.

4. H. Rogers Jr, Theory of recursive functions and elfective computability. New York: McGraw-Hill, 1967.

5. M. G. Rosinas, “Chastichnie stepeni i r-stepeni”, Siberian Mathematical Journal, vol. 15, no. 6, pp. 1323-1331, 1974.

6. S. B. Cooper, “Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense”, The Journal of symbolic logic, vol. 49, no. 2, pp. 503-513, 1984.

7. M. G. Rosinas, “Operacia skachka dlja nekotorih vidov svodimosti”, VINITI Dep, pp. 3185-76,

8. K. McEvoy, “Jumps of quasi-minimal enumeration degrees”, The Journal of symbolic logic, vol. 50, no. 3, pp. 839-848, 1985.

9. J. Case, “Enumeration reducibility and partial degrees”, Annals of mathematical logic, vol. 2, no. 4, pp. 419-439, 1971.


Рецензия

Для цитирования:


Солон Б.Я. Степени перечислимости ограниченных множеств. Моделирование и анализ информационных систем. 2022;29(2):104-114. https://doi.org/10.18255/1818-1015-2022-2-104-114

For citation:


Solon B.Y. Enumeration Degrees of the Bounded Sets. Modeling and Analysis of Information Systems. 2022;29(2):104-114. (In Russ.) https://doi.org/10.18255/1818-1015-2022-2-104-114

Просмотров: 38


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)