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-Goedel 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. Goedel'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 12, April 19, April 26, May 3, May 10, May 17
Seminar Room von Neumann (April 12, 19), Seminar Room Goedel (April 26 - May 17) Favoritenstrasse 9, ground floor
begin: April 12, 2010.

Preliminary Meeting:

Monday, March 8, 11:30-12:30 Seminar Room Zemanek, Favoritenstrasse 9, ground floor