TTMS26. The degree structures induced by algorithmic reducibilities
Dr. Mars Yamaleev, Kazan Federal University, Russia
Title: The degree structures induced by algorithmic reducibilities.
Abstract: It is well known that all programs for a fixed language of programming can be effectively coded and enumerated. Does there exist a program which can determine whether a program with code "e" will eventually stop? This question is known as the halting problem and put a great impact for the development of mathematical logic and theory of algorithms in 1930-th. It has a lot of connections with Hilbert's 10-th problem which asks: does there exist a unique method that allows to say whether given Diophantine equation has a solution? The problems obtained negative solutions in the past century.
This means that we don't have an algorithm for recognizing such codes "e" whose programs will stop. On the other hand, we have an algorithm for enumeration of such codes, which originates the set of the halting problem K. More surprisingly, there is a whole world of sets which are algorithmically reducible to K, and, in particular, Turing reducible to K. In the talk we will consider the degree structures induced by these sets via different algorithmic reducibilities. We will consider algebraic and model-theoretic properties of these structures, and discuss some recent achievements in this area.