Computability Theory (WISM430)(Recursion Theory)
Lecturer: Jaap van Oosten.
There is no exercise class
This course will be given in the fall of 2011.
The course is on Tuesdays, 13:15-15:00, in MIN 207 (weeks 37--45) and WIS 610 (Note! Room was changed!) (Weeks 46--51)
The course will be concluded by a written exam. Here is an old exam with solutions. Another one, without solutions. Yet another one.
During the course, there will be three "bonus tests". These are small quizzes (you have 15 minutes). Every bonus test earns you at most half a point (so in total the maximum you can get is 1.5). The total you get will be added to your exam result.
Literature: We use Lecture Notes. These are in Dutch; a translation is in progress.
We shall also give an introduction to Gödel's Incompleteness Theorems. For this, we use the text Introduction to Peano Arithmetic.
Description of the subject
Many mathematical challenges are of the form: find a "definite method", or "algorithm", in order to determine some property of a mathematical object. Examples are:
1. Hilbert's 10th problem: determine whether or not a polynomial equation with integer coefficients has a solution in the integers;
2. (Also posed by Hilbert) Find an algorithm to determine whether or not a given sentence of first-order logic is valid;
3. Given a finite presentation of a group, determine for two representations of elements (i.e., "words"), whether or not they represent the same element;
4. Given a finite-dimensional CW-complex, determine whether or not its fundamental group is trivial;
and so on.
But, do such algorithms exist? Such a question can only be answered once we have a definite notion of what an algorithm is. In 1936, Alonzo Church and Alan Turing gave, independently of each other, definitions of what it means that something is "algorithmically computable"; the definitions turn out to be essentially equivalent. Moreover, the definitions have stood the test of time: no "intuitively algorithmically computable" property has been found, which does not fall under the Church-Turing definition.
In this course, the theory of such algorithmically computable functions will be developed (in the Church-Turing sense). As application, for some of the challenges above it will be seen that they cannot be solved algorithmically (that is, the algorithm asked for in the challenge does not exist).
The theory of computable functions has extensive applications in Logic, but also in Computer Science.
Overview of the material treated in the course
Not always there will be time enough to treat all material in the lecture. What is listed is the required reading for the exam.
- Week 37: introduction and definition of register machines and computable functions. Proof that computable functions are closed under primitive recursion (1.4).
- Week 38: remainder of 1.1; 1.2; 1.3 up to Proposition 1.14.
- Week 39: remainder of 1.3; 1.4 up to definition of coding of computations.
- Week 40: remainder of 1.4; 1.5 (Smn-theorem and recursion theorem).
- Week 41: remainder Chapter 1; 2.1; 2.2 up to (and including) Proposition 2.6.
- Week 42: remainder 2.2. Bonus Test.
- Week 43: 2.3: theorems of Myhill-Shepherdson and Rice-Shapiro.
- Week 44: 2.3: theorems of Friedberg (2.18) and Kreisel-Lacombe-Shoenfield (without proof); 2.4; 3.1.
- Week 45: No lecture
- Week 46: 3.2 up to 3.2.1.
- Week 47: 3.2.1, 3.3 up to Corollary 3.18.Bonus Test
- Week 48: remainder of 3.3, 3.4 and 4.1.
- Week 49: start with Peano Arithmetic: philosophical introduction and from the text "Introduction to Peano Arithmetic": up to and including Exercise 7.
- Week 50: From "peano Arithmetic": remainder Chapter 1, up to and including Theorem 1.13. Also: definition of Delta_1 formula (just above Exercise 22).
- Week 51: An impression of Gödel's First Incompleteness Theorem (Chapter 2, up to 2.3). Bonus Test
- Week 2: Exam January 10, 14:00-17:00, room 610.
Back to my teaching page