|
Instructors: Prof. Dr. phil. nat. Ulrich Kohlenbach
Event type:
Lecture & Exercise
Org-unit: Dept. 04 - Mathematics
Displayed in timetable as:
Computability Theory
Subject:
Crediting for:
Hours per week:
3
Language of instruction:
Englisch
Min. | Max. participants:
- | -
Course Contents:
This course gives a brief introduction to classical recursion (computability) theory culminating in the solution of Post’s problem by the priority method (Friedberg/Muchnik). Table of contents: the basic machine, definition of recursive functions, codes and indices, Kleene normal form theorem, Kleene recursion theorem, Church’s thesis, relative recursion, arithmetical hierarchy, recursively enumerable relations, Turing degrees, solution of Post’s problem, computable functionals.
Literature:
Shoenfield, Joseph R.: Recursion Theory. ASL and A K Peters, 96pp., 2001.
Cutland, Nigel J.: Computability. Cambridge University Press 1980.
Preconditions:
recommended: Introduction to Computability Theory
Alternatively: Logic as taught in CS programmes
|
