Computability DCS301

Computability DCS 301

QMUL - Semester 6 - Winter 2009
Lecturer: Dr Gianluigi Bellin

Information:

Two lectures each week:
Tuesday 14:00-15:00 Computer Science Building Room 3.38
Wednesday 11:00-13:00 Francis Bancroft Building Room 1.13

Homework discussion:

Lecturer's Office hours: Tuesday after 4pm ? , Room CS 403

Teaching Assistant:
- Sirvan Yahyaei
  Office hours: tba, Room CS 416
  Email contact: sirvan@dcs.qmul.ac.uk
If you cannot meet the letturer or the TAs during office hours for good reasons (e.g., a coincident class), sent them Email to agree a meeting time.

You need to do a certain number of homework assignments (at least 5).

WARNING!
In order to obtain uniformity in evaluation, the Department has advised us to adopt a standard criterion for passing the class:
You must obtain 30/100 in the exam and then 40/100 in the overall mark, which is determined as follows:
- Exam will be worth 70% of the final mark.
- Coursework will be worth 30% of the final mark.

Comment: The policy that you must reach at least 40/100 in the exam has been abolished. But notice that now the mark in the coursework also counts for passing the course.

If you try to pass the course without doing any coursework, you need to get almost 60/100 in the exam.
If you manage to get only 30/100 in the exam, then you need to obtain 63/100 in the coursework in order to pass the course.
If you get 85/100 in the coursework, then you can obtain an A mark (70/100) by just getting 64/100 in the exam.

Apart from these calculations, if you do your coursework (and you understand what you've done), then it will be easy to do well in the exam.

Textbooks:

G.S.Boolos, J.P.Burgess and R.C.Jeffrey Computability and Logic
Fourth Edition, Cambridge UP 2002 ISBN 0521 00758 5 paperback
(This is a very good book on computable functions, but it requires a careful reading. Prerequisites are taught in the courses DCS117 Discrete Structures and DCS125 Logic and Proof.)

E.Kinber and C.Smith Theory of computing. A Gentle Introduction
Prentice Hall ISBN 0-13-027961-7 hardcover
(The book covers the part of the course on Automata Theory and Languages. As the title says, it is a clear and readable introduction to the subject.)

J.E.Hopcroft, R.Motwani and J.D.Ullman Introduction to Automata Theory, Languages, Logic and Computation
Second Edition, Addison Wesley ISBN 0 201 44124 1
(The classic text on Automata Theory, expanded with interesting examples in the second edition.)

P.Cohn Algebra, Vol 1, Chapters 1 and 2.

Handouts.
Handout 1. Sets, etc. set.pdf, set.ps

FSM.pdf

FSM.ps

pdf

R.Graham, B.Rothschild, J.Spencer. Ramsey Theory, 1980, J.Wiley and sons: pp.1-9, p.76

Useful link: Computer Laboratory, University of Cambridge
Course on Regular Languages and Finite Automata . Principal Lecturer: Prof Andrew Pitts.
Course on Computation Theory . Principal Lecturer: Prof Andrew Pitts.

Timetable:

Weeks 1 and 2. Prerequisites: Sets, Relations, Orderings, Functions, Cardinality, Proofs by induction, etc.
Russell's paradox. Cardinality of N, Z, Q and R. Cantor's theorem.
Slides Week 1: intro page 1, sets page 2, Russell page 3, barber page 4, axioms page 5 in .pdf format.
Slides Week 2: rels p. 9, eqr-prt p. 10, maps p. 12, inv-df p. 13, inv-th p. 14, count p. 15, uncount p. 16 in .pdf format.
Handout 1. Sets, etc .pdf, .ps
Read Chapters 1 and 2 of G.S.Boolos, J.P.Burgess and R.C.Jeffrey Computability and Logic

Weeks 3, 4, 5, 6 and 7. Finite State Machines, Deterministic and Non Deterministic Automata, Regular Languages, Pumping Lemma for Regular Languages, Context-free grammars.

Slides Week 3: intro 2.1, FSM-df 2.2, comment 2.3, example 2.4, diagram 2.5, parity 2.6, add 2.7, mult 2.8 in .pdf format.
Readings Weeks 3 and 4:
Handout 2. Finite State Machines, etc .pdf, .ps
Lecture Notes and slides by Prof Andrew Pitts Reg.Lang.Fin.Aut.
(Chapters 1-4 on Regular expressions, Regular Languages, Kleene's Theorem)
Week 7. Here you find Dr Paulo Oliva's slides

Readings Weeks 5, 6 and 7:
Handout 3. Pumping Lemma for Regular Languages pdf ps
Lecture Notes and slides by Prof Andrew Pitts Reg.Lang.Fin.Aut
(Chapters 5, 6 on Pumpig Lemma, Grammars)
Consult Kinber and Smith, Theory of Computing
Consult Hopcroft, Motwani and Ullman Intro. to Automata Theory, Languages, Logic and Computation.

Week 8. Review of Languages and Automata and Overview of partial recursive functions.

Week 9. Primitive Recursive Functions and relations. Read Handout 4.pdf

Weeks 10. Register Machines, Register-Machine computability. Abacus Machines

Week 11. Universal Turing Machines. Unsolvability of the Halting Problem.
Slides on Turing machines
what's-a-TM?, definition, configurations, ex 1: palindroms., ex 2,3: shift, succ in .pdf format.
Turing computability
basic definitions, universal TMs, How UnTM simulates TMs example
Existence of non-Turing computable functions. Universal TM.
argument by cardinality, Proof.
Unsolvability of the halting problem.
The Halting Problem, conclusion.
Church's thesis. Decidability, semi-decidability
Church's Thesis, Evidence for CT, decidability, semidecidability, in .pdf format.
Read Lecture Notes and slides by Prof Andrew Pitts Computation Theory,
sections on Register machines, A universal register machine. The halting problem. Turing machines and the Church-Turing thesis, Recursive and r.e. sets.
Read G.S.Boolos, J.P.Burgess and R.C.Jeffrey Computability and Logic Chapters 1-8.

Week 12. Recursive functions, partial and total.
Read Lecture Notes and slides by Prof Andrew Pitts Computation Theory, sections on Primitive recursive functions, Recursive functions, partial and total.

More advanced topics:
- Recursively Enumerable (r.e.) Sets: Slides: Accepting and deciding (Post Thm), Fundamental Thm of r.e. sets, r.e.sets (proof), r.e.sets (cont.), r.e.sets (concl.).
- The s-n-m theorem and the Recursion Theorem: see Wikipedia; see also Final Exam 2007 AMCM060 Questions 6.

Homework Assignments:

Homework 1. pdf (due on Fri Feb 6th 2009)
Model Solutions: pdf

Homework 2. pdf (due on Friday Feb 13th)
Model Solutions: pdf

Homework 3. pdf (due on Tuesday Feb 24th)
Model Solutions: pdf

Homework 4. pdf (due on Wednesday March 25th)
Model Solutions: Claire_Tafanelli
Another solution of the register machines for quotient and remainder based on the algorithm of division by subtraction is in the following coursework: Zabihullah_Gharghasht

Homeworks 5-6. pdf
Some comments on Courseworks 4-5-6. pdf

Review Session - Exam Preparation:

Please notice that Coursework 5-6 serves also as a review paper.

Question 1. Automata and Pumping Lemma.
Handout 2. Finite State Machines, etc., Slides Week 3; Prof Pitts Lecture Notes and Slides, Chapters 1-4.
Homework 2, Questions 1 and 2; Homework 5, Question 1, with Solutions and comments.

Question 2. Pumping Lemma and applications.
Handout 3. Pumping Lemma for Regular Languages; Prof Pitts Lecture Notes and Slides, Chapters 5,6.
Homework 3, Question 3; Homework 5, Question 1.

Question 3. Primitive Recursive Functions.
Handout 4. G.S.Boolos, J.P.Burgess and R.C.Jeffrey Computability and Logic, Chapters 6 and 7,
Homework 6, Question 1.

Question 4 Halting Problem
For Turing Machines see Slides on Turing Machines, Turing Computability, Universal Turing Machines, Unsolvability of the Halting problem; R.E. sets and Church's thesis. Homework 5, Question 2. Homework 6, Question 2.

Question 5 Register Machines
For Register Machines, see slides on Abacus Machines; see also Prof Pitts Lecture Notes on Computability.
See also Homework 4, Question 2.

EXAMS in previous years:

FINAL EXAM 2002 with solutions!!! pdf ps

FINAL EXAM 2005 with solutions!!! pdf ps

FINAL EXAM 2007 with solutions!!! CS301 AMCM060