Definability and global degree theory
S. Barry Cooper · Cambridge University Press eBooks · 2017
Gödel's work [Gö34] on undecidable theories and the subsequent formalisations of the notion of a recursive function ([Tu36], [K136] etc.) have led to an ever deepening understanding of the nature of the non-computable universe (which as Gödel himself showed, includes sets and functions of everyday significance). The nontrivial aspect of Church's Thesis (any function not contained within one of the equivalent definitions of recursive/Turing computable, cannot be considered to be effectively computable) still provides a basis not only for classical and generalised recursion theory, but also for contemporary theoretical computer science. Recent years, in parallel with the massive increase in interest in the computable universe and the development of much subtler concepts of 'practically computable', have seen remarkable progress with some of the most basic and challenging questions concerning the non-computable universe, results both of philosophical significance and of potentially wider technical importance. Relativising Church's Thesis, Kleene and Post [KP54] proposed the now