Elementary Recursion Theory



Time and place:

  • Time and place on appointment


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