Seminar: Logic and Algebra | LTG

Seminar: Logic and Algebra

Lecturer	Prof. Dr. Gerhard Jäger, Prof. Dr. George Metcalfe, Prof. Dr. Thomas Strahm
Assistant	Dr. Kentaro Sato
Lecture Number	W6081
ECTS credits	depend on students' majors.
Start	September 22, 2011
Time	Thursday, 10-12
Venue	Lecture room A97 Gebäude der Exakten Wissenschaften ("ExWi" building) Sidlerstrasse 5
Content	This seminar provides an introduction into computability theory. Starting off from some basic results about computable functions as presented e.g. in the bachelor course "Berechenbarkeit und Komplexität" we discuss some central results like the fixed point theorem and Rice's theorem. In a later part we turn to the classification of computable and more general number-theoretic functions according to their logical complexities. In this context also functionals of higher types may be considered.
Requirements	Basic knowledge in mathematical logic and/or theoretical computer science.
References	Main reference: Peter G. Hinman, Recursion-theoretic hierarchies, Springer, 1978. Available online (campus) here: http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handl... Additional references: Wolfram Pohlers, Computability theory of hyperarithmetic sets, Lecture Notes, University of Muenster. Available online here: http://wwwmath.uni-muenster.de/logik/Veroeffentlichungen/lec/Pohlers/rek... Helmut Schwichtenberg, Recursion theory, Lectures Notes, University of Munich. Available online here: http://www.mathematik.uni-muenchen.de/~schwicht/lectures/recth/ws06/rt.pdf These texts are available online. Further instructions will be given during the seminar.
Repetition	Every semester with varying contents.
Homepage	http://www.iam.unibe.ch/~sato/morning_hs11/