<p>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!).</p>

<p>Rather, a senior undergraduate level course in <strong>mathematical logic</strong> is the typical prerequisite.</p>

<p>Traditionally since Gödel, mathematical logic is considered to have four parts (in no particular order):</p>

<ul>
<li>Set theory</li>
<li>Model theory</li>
<li>Computability theory</li>
<li>Proof theory</li>
</ul>

<p>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.</p>

<p>Both culturally and scientifically, computability theorists are, and consider themselves to be, part of the mathematical logic community and often study things like computable <em>model theory</em> or higher computability theory (which borders on <em>set theory</em>). Some mathematical maturity is also very helpful.</p>

CC BY-SA 3.0
2017-10-01T00:43:18.580Z
2017-10-01T00:48:45.313Z
2017-10-01T00:48:45.313Z
Bjørn Kjos-Hanssen
<p>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?</p>

<soft-question><computability>
Computability Theory prerequisites
Nikola
# Computability Theory prerequisites

(Asked by: username_0 on 2017-09-30)

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?

**Tags:** soft-question, computability


---

## 1 answers

### Answer by username_1 on 2017-10-01. Score: 7 | Accepted answer

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.


---

