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

*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.

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!**

*31.1.07—Lecture 1* Introduction 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 2* *Function*: *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 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)*.

- 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 4* Proof 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 5* Proof 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 6* *Alphabet*, *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 7* *Deterministic 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 8* *Nondeterministic 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 9* The *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 10* *Proof* 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 11* Example 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 12* Definitions 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 13* Formal description of the language *a ^{n}b^{n}c^{n}*; how to

- Prove that a
^{n}b^{n}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 14* *Proof* that a^{n}b^{n} 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 15* *Explanation* 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 16* *Computable 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 17* *Proof* 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 18* Introduction 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 19* Examples 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 20* Definition 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 21* *Recursive 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 22* Exam modalities and discussion of two exercises of last year's 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.

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.

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 @)