2.0 VU Theorie der Berechenbarkeit (185.203, SS 2009)

Lehrveranstaltungsleiterin: Alexander Leitsch

Computability theory is that part of theoretical computer science dealing with which problems are solvable by algorithms.

Not all problems can be solved. An undecidable problem is one that cannot be solved by any algorithm, even given unbounded time and memory. Many undecidable problems are known. The most well-known is the halting problem: given a program and inputs for it, decide whether it will run forever or will eventually halt.

Content:

The course gives an introduction to computability theory including topics like: Problems that computers cannot solve. Overview on some models of computation: Turing machines, register machines, Herbrand-Gödel computations and recursive functions. Church's thesis. Numberings of computable functions. Numberings of programs, the diagonal method, the s-m-n theorem. Universal programs. Recursive and recursively enumerable sets. The recursion theorem and Rice's theorem. Gödel's incompleteness theorem.

Reference Books: (parts of)

• H. Rogers: Theory of recursive functions and effective computability
• N.J. Cutland: Computability
• P. Odifreddi: Classical recursion theory

Time and Place:

Monday, 12:00 - 16:00
dates: April 4, April 11, May 2, May 9, May 16, May 23
Seminar Room Gödel, Favoritenstrasse 9, ground floor
begin: April 4, 2010.