The goal of the lecture is to investigate the theoretical models of computation of functions from the natural numbers to natural numbers and of subsets of the natural numbers. All reasonable notions turn out to be equivalent; important models are that of unlimited register machines and Turing machines. A special emphasis is given to the recursively enumerable subsets of the natural numbers; such a set is the range of a computable function from the natural numbers into itself. It is shown that there are unsolvable problems and uncomputable functions. Relations of difficulty among the recursively enumerable sets are established and the diagonal halting problem is shown to be the most difficult recursively enumerable set.

- Frank Stephan:
homepage.

- Midterm Examination: 01 March 2005, 0800-0900h, 20% of final mark;

Final Examination: 29 April 2005, Morning, 80% of final mark.

- Venue: Room S13#05-01

Tuesday 08.00-10.00h (lecture)

Wednesday 10.00-12.00h (half tutorial, half lecture). - Text Book: Computability - An introduction to recursive function theory by Nigel J. Cutland, Cambridge University Press, 1980.
- Assignments: 26.01.2005 ps-file, pdf-file; 02.02.2005 ps-file, pdf-file; 16.02.2005 ps-file, pdf-file; 02.03.2005 ps-file, pdf-file; 09.03.2005 ps-file, pdf-file; 16.03.2005 ps-file, pdf-file; 30.03.2005 ps-file, pdf-file; 06.04.2005 ps-file, pdf-file; 13.04.2005 ps-file, pdf-file.
- Ackermann Function: Some small values for the Ackermann Function from pages 46 and 47 in Cutland's Book can be computed with a Java Script Program.
- Formal grammars: This link goes to a Summary on formal grammar terminology in the online dictionary Wikipedia. It contains some examples of grammars and explains how words are generated by them. The relevant parts are also summarized in the homework for 16.02.2005.