|
|
Конференция международных математических центров мирового уровня
9 августа 2021 г. 14:30–15:15, Теория вычислимости и математическая логика, г. Сочи
|
 |
|
 |
|
|
|
The Theories of the Turing degrees and the bounded Turing degrees below 0’
М. М. Арсланов
Институт математики и механики им. Н. И. Лобачевского Казанского (Приволжского) федерального университета
|
| Количество просмотров: |
| Эта страница: | 104 |
|
Аннотация:
We discuss the structures of degrees under the Turing reducibility and the bounded Turing reducibilities, when the questions asked of the oracle are bounded by some natural conditions. We survey what is known about the algebraic structure and the complexity of the decision procedure for these degree structures. Typical algebraic questions include the existence of infima, distributivity, embeddings of partial orderings or lattices and extension of embedding problems.
Finally, we discuss some results and open problems concerning definability and the complexity of the decision problems for these degree structures.
|
|
Обратная связь: