CM10020—Computation II: Computability and Decidability

1    Textbooks

Main textbook:

Please consider also, for the second part of the course on automata:

2    News

29.1.07    There will be tutorials in Week 1, they will revise some background notions.

16.2.07    I distributed in class some slides on automata by Führmann. You can follow the part of the course on languages and automata on them, but, ideally, you should use the Hopcroft-Motwani-Ullman textbook.

16.2.07    Have a look at the 2006 exam paper.

12.4.07    In the week from 16 to 20 April, due to the absence of Tom Gundersen and Mark Price, the tutorials will be covered by Tom Crick and Jonty Needham. Tutorial groups will not be split, and students should go to the rooms indicated by their timetables.

3    Course Info

In the following, I will link some material distributed or used in the past for this course: please disregard any information related to the organisation of the course: it is possibly not valid any more. Also, keep in mind that I might change the presentation, sometimes substantially. The material we cover is clearly indicated below.

Usually, in every lecture I suggest some exercises, and then I report these suggestions on this web page. I always suggest exercises on this page after lectures. You are supposed to seriously try, and hopefully solve, all the suggested exercises before the next tutorials and lectures. In the tutorials, and in part also in the lectures, you can check the correctness of your solution and we will go through the difficulties you might have encountered. Be active! This is an easy course if you are active and follow these suggestions, but it becomes very difficult otherwise, and you risk to fail your exam!

Lectures and topics

31.1.07—Lecture 1    Introduction to the course, first basic definitions about sets and total, partial and injective functions.

2.2.07—Lecture 2    Function: surjective and bijective; domain and range of functions; enumerable sets; enumerability and Cantor's proof of non-enumerability of real numbers.

7.2.07—Lecture 3    Non-enumerability of the powerset of natural numbers (Cantor's diagonalisation) and enumerability of the set of positive or null rational numbers (Cantor's zig-zag).

9.2.07—Lecture 4    Proof that N × N, Nk and the set of of subsets of natural numbers whose size is less than a given k are enumerable; definition of encoding.

14.2.07—Lecture 5    Proof that the set of finite subsets of natural numbers is enumerable and relation between encoding and enumeration.

16.2.07—Lecture 6    Alphabet, Kleene star, language, string and first ideas on automata.

21.2.07—Lecture 7    Deterministic finite automaton (DFA), extended transition function and language recognised by a DFA, example of all these things.

23.2.07—Lecture 8    Nondeterministic finite automaton (NFA), extended transition function and language recognised by an NFA, example of all these things.

28.2.07—Lecture 9    The powerset construction, transforming NFAs into DFAs.

2.3.07—Lecture 10    Proof that NFAs and DFAs recognize the same languages; regular expressions and their meaning.

7.3.07—Lecture 11    Example of regular expression, informal definition of ε-NFA and transformation of regular expressions into ε-NFAs.

9.3.07—Lecture 12    Definitions of formal grammar, context-free grammar and regular grammar, with examples.

14.3.07—Lecture 13    Formal description of the language anbncn; how to transform a regular grammar into a regular expression.

16.3.07—Lecture 14    Proof that anbn cannot be recognised by a DFA; definition of Turing machine.

21.3.07—Lecture 15    Explanation on why Turing machines compute NN functions.

23.3.07—Lecture 16    Computable functions, proof that some NN functions are not computable.

18.4.07—Lecture 17    Proof of the fact that the diagonal and halting functions are not computable.

20.4.07—Lecture 18    Introduction to recursive functions; primitive recursive functions: successor, zero, projections, composition and primitive recursion.

25.4.07—Lecture 19    Examples of primitive recursive functions for addition and product; sketch of a proof that primitive recursive functions are total.

27.4.07—Lecture 20    Definition of the Ackermann function, lexicographic ordering and proof of the totality of the Ackermann function; definition of the minimisation function.

2.5.07—Lecture 21    Recursive functions and theorem about recursive functions being all and only the Turing-computable ones.

4.5.07—Lecture 22    Exam modalities and discussion of two exercises of last year's exam.

Material covered and to be prepared for the exam

Exercises

Consider looking into these exercises with worked solutions, made by Emma Jones and Richard McKinley for a past course. It is necessary to be able to do all the exercises suggested in class and in this page, in order to pass the exam with a good grade.

Try also the 2006 exam paper.

4    Tutors and Office Hours

Tom Gundersen and Mark Price.

When you want to talk to me, just drop me an email and we'll arrange for an appointment.

4.5.2007    Alessio Guglielmi    email (replace AT by @)