Elementary Recursion Theory (ERT)
- Dozent/in
- Dr. Wolfgang Degen
- Angaben
- Vorlesung
2 SWS, benoteter Schein, ECTS-Studium, ECTS-Credits: 2,5, Sprache Deutsch oder Englisch
Zeit und Ort: n.V.; Bemerkung zu Zeit und Ort: The first session will be held on Tuesday 25. o4. 2017 from 14:15 to 15:45 in room 00.133-128 (Animationslabor)
- Inhalt
- 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.
- Empfohlene Literatur
- (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
- ECTS-Informationen:
- Credits: 2,5
- Zusätzliche Informationen
- Erwartete Teilnehmerzahl: 5
- Institution: Lehrstuhl für Informatik 10 (Systemsimulation)
|
|