What are the prerequisite disciplines for Computability theory? How much is Theory of Computation, Automata Theory, etc and how hard would it be studying it without those prerequisites?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
Theory of computation and automata theory are not really needed for pure computability theory (but they are a very nice complement to computability theory and certainly help put it in perspective and relate it to the real world!).
Rather, a senior undergraduate level course in mathematical logic is the typical prerequisite.
Traditionally since Gödel, mathematical logic is considered to have four parts (in no particular order):
- Set theory
- Model theory
- Computability theory
- Proof theory
In computability theory you will learn things like the correspondence between $\Sigma^0_n$ sets in arithmetic and the Turing degree $0^{(n)}$, and of the Turing degrees of complete extensions of Peano Arithmetic.
Both culturally and scientifically, computability theorists are, and consider themselves to be, part of the mathematical logic community and often study things like computable model theory or higher computability theory (which borders on set theory). Some mathematical maturity is also very helpful.
answered Oct 1 '17 at 0:43