Steve Vickers: Models of Computation

Turing centenary 2012

The work of Alan Turing is fundamental to about half this module. 2012 is the centenary of his birth, and one celebration is on the website of the National Physical Laboratory where he worked after the 2nd World War helping to develop the Pilot Ace, one of the first electronic computers.

The NPL commissioned a short film "Piloting Computing" of interviews with some people who worked there at the time. (I have a particular interest in it because it was made by my daughter Harriet Vickers and one of her interviewees is my father Tom!)

Models of Computation

Lecturer: Steve Vickers
These is my material (mostly based on Achim Jung's) from when I gave the module in 2012.

Handouts

Handouts containing lecture notes and exercises will be provided after each lecture. They can also be accessed here (in PDF format).

Spare copies are kept in the School Library.

PDF versions of some of the lecture slides can also be accessed here, but they are best viewed on-line in colour. Printed copies will not be made available.

General information

Week by week: Handouts will normally be made available the Friday before the lecture, and the slides after the lecture. Handouts and slides for future weeks are from last year and are for reference only. There may be changes this year and in particular the exercises will be different.
Solutions to coursework will be made available after the handin date.

  1. Finite State Machines and Regular Expressions: handout, solutions, slides, applets to demonstrate non-deterministic finite automata and non-deterministic finite automata with epsilon-moves.
  2. Regular Languages: handout, solutions, slides.
    For more on loop invariants and Warshall's algorithm, see Reasoned Programming, chapters 10 (p.141) and 13 (p.176).
  3. Context-free languages and pushdown automata: handout, solutions, slides
  4. The Halting Problem: handout, solutions, coursework notes by Chuangjie Xu, slides, Geoffrey Pullum's poem "Scooping the Loop Snooper"
  5. More on decidability: reducibility proofs: handout, solutions, coursework notes by Chuangjie Xu, and some more, slides.
  6. Turing machines: handout, solutions, slides.
    The homework in the printed handout is wrong. See the on-line handout for the correct version.
  7. Church's Thesis: handout, solutions, slides.
  8. Complexity: handout, solutions, coursework notes by Chuangjie Xu, slides.
  9. P versus NP: handout, non-examinable appendix with proof of Cook's theorem, solutions, slides, $1,000,000 prize offered by Clay Mathematics Institute.
  10. The λ-Calculus: handout, solutions, slides.
  11. More on the λ-Calculus: handout, solutions, slides.

Revision notes

For solutions and feedback on exams, see previous exam papers.

Continuous assessment

This contributes 20% to the module mark and consists of the following. Every handout will contain "Quickies", "Classwork" and "Homework". Quickies are small exercises best done shortly after the lecture to experiment with the new concepts. They are generally unassessed. If any Quickies are assessed, they should be handed in to the tutor during the exercise class. The classwork exercises are to be done during the exercise classes and your work will be collected by the tutor for marking at the end of the class. Homework must be handed in through one of the departmental pigeon holes on the Ground Floor (next to the General Office). Homework is due Mondays, 2pm. This is one week after they have been issued in the lecture. Late submissions will not be accepted because we will provide model answers to all exercises. If you have a serious reason for not being able to complete a particular assignment, then see someone from the Welfare Team. (The precise procedure is explained in the Student Handbook.) If your explanation for absence is accepted then we will ignore the relevant pieces of assignment in the calculation of your mark.

Marks will be assigned on the basis of your performance in both classroom and homework exercises. You will be able to check the marks which have been recorded against your name by visiting this web page. Marked work will normally be returned at the exercise classes two weeks after it was set.

Part of the continuous assessment mark will be given for participation in Peerwise.

Policy on plagiarism

You are encouraged to work in small teams during the exercise classes and to ask for help from the tutor. You will, however, have to submit your work individually. Homework exercises are of a style similar to those appearing in the May examination, and we recommend that you attempt them individually, but you may still find it helpful to discuss the assignments with others. In any case, work submitted must be formulated by yourself. If we find evidence of plagiarism then we will award zero marks, irrespective of whether you copied from others or whether your work was copied by others. More serious cases will be dealt with according to the School's policy on plagiarism.

Anonymous marking

We are required to mark anonymously wherever possible. There is no reason why we should not follow this rule for the exercises in this course. Please note, however, that this means that you always have to write your registration number on your submitted work. Scripts which do not contain the registration number will have to be ignored by us.

Final exam

The exam takes place in May and lasts 1.5-hour. It is marked on a scale from 0 to 100 but contributes only 80% to the module mark.

If you choose not to participate in the continuously assessed exercises, then you have to obtain 50% of the exam marks in order to pass the module!

You can access previous exam papers.

Resit exam

There is one resit opportunity for this module in August. It contributes 100% to the module mark -- the exercise mark will not be carried forward.

Note that the 2012 resit exam will be in the same format as last year's main paper, for 2010-11, and not this year's.
You will be asked to attempt all the questions, and different questions are worth different amounts of marks.

Peerwise

Please sign up for this module on Peerwise immediately; it only takes a few minutes.

Part of the continuous assessment mark will be given for participation in Peerwise. See the instructions for students on that page.

To gain points, you must write at least one multiple-choice question on a topic covered in the module, and answer at least three other questions.

A further part of the mark may be given as discretionary bonus points. The bonus marks may be awarded for active participation (e.g. leaderboard status), but in particular for writing insightful questions.

The more questions you create, answer, comment on, etc, the more you will learn and the more you will help other students on the module. If a fair number of students contribute good questions, there will be plenty of revision material for everyone before the exams. You may also enjoy winning badges and trying to get on the leaderboard.

You need to register on the Peerwise server.

  • The course ID for this module is 5945.
  • Your "identifier" on Peerwise is the same as your Bham student ID number.
  • You can choose any username and password when registering.
  • Please tag your questions with appropriate topics, so that others can find them more easily.

Textbooks

It is not necessary for you to buy a textbook for this course as the handouts are sufficiently detailed for revision and self-study. Some students, however, do like to see the material explained by another author and this can help to understand the more difficult parts. In this case we recommend that you examine the textbooks in the School Library first before you commit any money.

Sipser: Introduction to the Theory of Computation. PWS Publishing, 1997.

The first part on finite automata is excellent and gives many examples and detailed explanations. The later chapters get rather mathematical, but on the whole this book is good cover for the module.

Harel: Computers Ltd: What they really can't do. Oxford University Press, 2003.

A well-written and non-technical introduction to the fields of uncomputable problems (e.g., "Halting Problem") and NP-completeness.

Martin: Introduction to Languages and the Theory of Computation. McGraw-Hill.

The strength of this book is the many worked examples. What I don't like so much is its reliance on mathematical formalism (and the fact that it starts with two chapters on mathematical background). Like the books before, it does not cover everything we do in the course.

Jones: Computability and Complexity: From a Programming Perspective. MIT Press.

This is one of the very few books which subscribe to the view that undecidability can be explained without Turing machines (the course notes being another such text). However, the underlying formalism is that of functional programming which not all of you will be familiar with.

Michaelson: An Introduction to Functional Programming through Lambda Calculus. Addison-Wesley.

This is a nice gentle introduction to the λ-calculus, leading towards functional programming. The early chapters are very accessible.