CM10020—Computation II: Computability and Decidability

1Textbooks

Main textbook:

• Computability and Logic
  4th edition
  by George S Boolos, John P Burgess, Richard C Jeffrey
  Cambridge University Press

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

• Introduction to Automata Theory, Languages and Computation
  2nd edition
  by JE Hopcroft, Rajeev Motwani, Jeffrey D Ullman
  Addison Wesley

2News

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

16.2.07I 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.07Have a look at the 2006 exam paper.

12.4.07In 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.

3Course 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 1Introduction to the course, first basic definitions about sets and total, partial and injective functions.

• Exercise: formally define the notion of partial and total function by using set terminology (hint: use the product of sets).
• You can find useful Führmann's slides (part 1).

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

• Before the next lecture, please read Cantor's theorem about the powerset of the set of natural numbers.
• Do all the examples and exercises that you find in Führmann's slides (part 1) and problems 1.1, 1.2 in the textbook.

7.2.07—Lecture 3Non-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).

• Before the next lecture, please try to prove that the set of rational numbers, N × N, and N^k are enumerable.
• Führmann's slides (part 2) might be helpful.

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

• Before the next lecture, please try to prove that the set of finite subsets of natural numbers is enumerable.

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

• Please try by yourself all the exercises in Führmann's slides (part 2): it is necessary that you are able to solve all of them without hesitation.
• This concludes the first part of the course, dedicated to enumerability; I suggest problem 2.1 in the textbook.

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

• You find definitions in slides on automata by Führmann and in the Hopcroft-Motwani-Ullman.
• Please try to express formally the language of strings over the alphabet {0,1} containing three consecutive 0s.

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

• Exercises: give DFAs accepting the following languages over the alphabet {0,1}: 1) the set of all strings starting with 0 and with two consecutive 0’s (not necessarily at the end); 2) the set of all strings ending in 00. Exercise 2 is moderately challenging.
• Before the next lecture, please try to design a DFA which accepts strings of {0,1}* whose tenth symbol from the right is a 1.

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

• Exercise: design an NFA which accepts strings of {0,1}* whose tenth symbol from the right is a 1.

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

• Exercise: design an NFA, with at most four states, recognising the set of strings of 0s and 1s such that there are two 0s separated by an even number of positions. Then, construct a DFA recognising the same language, by using the powerset construction. For example, 00, 011110 and 011100 are all strings of the language, while 010 is not.

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

• Do the exercises at page 14 of the notes.

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

• Define the transition function and extended transition function of an ε-NFA, with the help of the notes.
• Formally prove the proposition at page 17 of the notes (on the equivalence of languages of regular expressions and ε-NFAs obtained from them).
• Please do the exercises suggested so far, all of them.

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

• Convert each of the following regular expressions to an ε-NFA: 01*, (0+1)01, 00(0+1)*. Then, convert each ε-NFA into a DFA.
• Would you be able to describe formally which language the grammar
  S → abc
  S → aSBc
  cB → Bc
  bB → bb
  produces? Can you prove that what you describe is the language produced by the grammar?

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

• Prove that aⁿbⁿ cannot be recognised by a DFA.
• Consider the Parity Checker DFA at p. 25 of the notes: obtain a regular grammar from it, then transform it into a regular expression, and simplify the expression. In plain English, which language does the automaton recognise?
• Please do the exercise on palindromes at the bottom right of p. 22, in the notes.

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

• You find Turing machines in Führmann's slides (part 3), which I distributed in class today.
• Do the first four exercises in the 2006 exam paper. You should be able to do three of them in two hours.

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

• Please do one of the exercises at pp. 27, 28 and 29 in Führmann's slides (part 3).
• Please revise the notions of enumeration and encoding, and prove that the set of functions N → N is not enumerable.
• Think about whether all functions N → N can be computed by a Turing machine.

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

• Please do the exercises at pp. 30 and 31 in Führmann's slides (part 3).
• Prove in detail that the set of N → N functions is not enumerable, by using Cantor's diagonal argument.
• Show how to enumerate Turing machines by first encoding them into natural numbers; spell out all the details.

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

• Try to reconstruct the arguments of the proofs seen in class by yourself.

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

• You can find these topics also in Führmann's slides (part 4).
• Define the predecessor function as a primitive recursive function.

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

• Please define a primitive recursive function for the exponential and the factorial functions.

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

• Please write a program and compute A(4,2), where A is the Ackermann function.

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

• You can read chapter 8.1 of the textbook for a clear proof of the theorem, which was only sketched in class; Führmann's slides (part 5) can help.
• Devise some reasonable way of assigning code numbers to recursive functions (in other words, how would you define their encoding?).

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

Material covered and to be prepared for the exam

• Chapters 1,2, 3, 4.1, 6 and 8.1 (without the details) of the Boolos-Burgess-Jeffrey. The Ackermann function is defined in example 7.23 in the textbook, but the definitions in Führmann's slides (part 4) and in Wikipedia are clearer.
• Up to page 28 of these notes.

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.

4Tutors 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.2007Alessio Guglielmiemail (replace AT by @)