Recursive Function Theory

1.

Definition of recursive and partial recursive functions. Recursive and recursively enumerable sets. Definability in arithmetic of recursive and r.e. sets. Church's Thesis.

2.

Unsolvability of the halting problem, and sample applications.

3.

Elementary recursive function theory. The recursion theorem and the enumeration and parametrization ($s$-$m$-$n$) theorems.

4.

Turing reducibility and degrees of unsolvability. The arithmetical hierarchy, $\Sigma_n$ and $\Pi_n$-sets for each integer $n$.