## Elementary Recursion Theory

### Lecturers

### Details

#### Time and place:

- Time and place on appointment

#### Content

Another term for Recursion Theory is Computability or Computation Theory.

Elementary R T is R T on the natural numbers N = {0,1,2,...}, in contradistinction to Higher R T on larger and more complicated sets.

We´ll start the lecture with defining the n-ary primitive recursive functions, for n = 1,2,3, ...

These functions are vastly more comprehensive than computer scientist can make use of, and they have already a very rich theory.

Next we´ll give two definitions of the general recursive function on N:one is via Turing machines, the other is by induction.

Then come the recursively enumerable(or semi-decidable)sets

Finally we´ll use these recursion-theretic tools to show some formal theories decidable, and some others undecidable.

#### Recommended Literature

(1) H. Rogers: Theory of recursive functions and effective computability, McGraw-Hill, 1967 (2) J.D. Monk :Mathematical logic, Springer, 1976 (3) P. Odifreddi :Classical recursion theory, vol. I, II, North-Holland, 1989,1999

#### Additional information

Expected participants: 5