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 enumerable set.