Recursion theory. Computational aspects of definability (Q2260474): Difference between revisions

The book contains the study of the structures of degrees arising from two key notions of reducibility, the Turing degrees and the hyperdegrees, using ideas and techniques beyond those of classical recursion theory. The book consists of four main parts. The Part I of the book entitled ``Fundamental theory'' contains six chapters which develop the fine structure theory of the constructible universe, the theory of \(\Pi_1^1\)-sets, the ramified analytical hierarchy, and set theory. The Part II (The story of Turing degrees) contains three chapters and it focuses on the structure of Turing degrees. In this part, the authors discuss the classification of the jump operator in relation to Martin's conjecture, the construction of \(\Pi_1^1\)-sets with the help of inductive definition. The last chapter of this part contains degree-theoretic independence results. Part III (Hyperarithmetic degrees and perfect set theory) is devoted to the study of hyperdegrees. It contains two chapters. The chapter ``Rigidity and biinterpretability of hyperdegrees'' contains the proof of the rigidity of the structure \(\langle {\mathcal D}_h\leq\rangle\) of the hyperdegrees and its biinterpretability with second-order arithmetic. These results were obtained by T. A. Slaman and W. H. Woodin. In this chapter, the authors present a more elementary proof of the rigidity of \(\langle {\mathcal D}_h\leq\rangle\) due to R. A. Shore. The biinterrpretability of the structure of hyperdegrees with the second order arithmetic follows as an application of rigidity. The last Part IV (Higher randomness theory) contains four chapters and is devoted to the study of higher randomness, i.e. to the study of algorithmic complexity problems of randomness using techniques and ideas from hyperarithmetic theory and set theory. The last chapter contains a list of open questions in hyperarithmetic theory, set-theoretic problems in recursion theory and open problems in higher randomness theory. The book ends with a very interesting and a huge interview with Professor Gerald Sacks conducted by the first author of the book and Yang Yue in June 2009. As the authors of the book write, ``it is fitting to conclude the book with a tribute to one whose work has arguably substantially shaped the development of recursion theory, both classical and higher, in the last century.'' This is a very well written book by researchers who contributed with significant results to the field, the treatment is mathematical rigourous, with important open problems, and an up-dated list of references. The book is suited for advanced courses and research.