\(\Pi_1^0\) classes, Peano arithmetic, randomness, and computable domination. (English) Zbl 1197.03045

The paper provides an overview of research and results obtained in the study of \(\Pi_{1}^{0}\) classes, Peano arithmetic, randomness and computable domination. Those topics have been – from the historical point of view – topics of interest in computability theory. They are still a source of problems and ideas. Links and connections between these topics are indicated. Their meaning for modern research is stressed.


03D25 Recursively (computably) enumerable sets and degrees
03C62 Models of arithmetic and set theory
03D30 Other degrees and reducibilities in computability and recursion theory
03D32 Algorithmic randomness and dimension
03F30 First-order arithmetic and fragments
Full Text: DOI