Computability Theory (MA3219)
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
- Frank Stephan:
- 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.
- 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
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.