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
Tutors: Zaid Alzobaidi, Masoud Koleini, Chuangjie Xu, Maxim Strygin
Additional help from Asiri Rathnayake

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

  • The revision lecture is 10.00, Monday 23 April, NG02 Biosciences.
  • Here are slides from last year's revision lecture.
  • Note that the format of the 2012 exam is different from previous years.

    • Academic Services have an exam papers database giving access to past papers. For last year, here are the 2011 paper and its model answers.

    To help prepare you for this year's exam, here is my feedback to last year's class on how the exam questions were answered in general.

    1. (Regular languages) Average 55%

    Mostly OK. Part (d), however, on the pumping lemma, was disappointing. Most of the answers looked like guesswork and pattern matching rather than intelligent students trying to think something through. Here's my answer.

    If it is regular, then there is a pumping length n (say). Consider the acceptable string "1n:1n" (in other words, there are two integers, and each is written with a string of n digits 1). Somewhere in the first 1n there is a pumpable substring, but as soon as we pump it the first integer becomes bigger than the second and so the string becomes unacceptable. Hence n cannot be a pumping length and the language cannot be regular.

    One common mistake was to think the pumping number is the number of times to pump.

    2. (Context free grammars) Average 48%

    Definitely a question where people's brains switched off. In fact by the time I'd marked questions 1 and 2 I was worried the whole class was going to fail and I was going to spend all September marking resits. (However, the high marks on questions 4 and 5 removed that worry.)

    A key part to this kind of question is understanding what the grammar is really about, but in fact parts (b) and (c) tell you.

    Part (a): When you argue that fffccf is not in the language, your argument needs to be fairly watertight, that there are no loopholes for getting a derivation in a sneaky way.

    One valid argument is that any S-string has to end in a c, and I gave full marks for answers that made some justification of this. However, surprisingly many answers claimed that no S-string could have two c's together. This is false - consider ffffcc.

    Part(b): Seemed to bemuse people. Bearing in mind that the property for S-strings is "the credit, starting from 0, finishes at 0 and never goes negative", the similar property for T-strings is going to be similar. In fact it is "the credit, starting from 0, finishes at 1 and never goes negative". Most answers were not at all similar.

    Part (c): Not many correct answers. We didn't have many examples of deterministic pushdown automata in the course, but this one is not difficult if you think about how a machine might use the size of a stack to represent credit stored. Each input f pushes some symbol (it doesn't matter what) on the stack, and each input c must pop two symbols. Think of the stack as a pile of 50p's not yet spent on cans.

    If you reproduced the standard way of making a non-deterministic PDA you got a few marks but not many.

    3. (Halting problem) Average 45%

    The worst question. Two classic errors were common: (i) trying to remember the proof of undecidability for the halting problem, and adapt it; (ii) reducing the method call problem to the halting problem instead of the other way round.

    4. (Turing machines) Average 73%

    Obviously this question was too easy.

    5. (Lambda calculus) Average 70%

    Again, you seemed to find this easy. The main mistake (important in (a)) was to misremember the bracketing rules.

    Timetable

    Revision lecture

    Monday 23 April 2012, 10.00--10.50am, Room NG02 Biosciences (Building R27)

    Lecture

    Mondays, 9:00--10:50am, Room E102 Biosciences (Building R27)

    Exercise Classes

    Tuesdays, 2:00--2:50pm

    Tutor groups

    There are four tutor groups.
    For full lists, click the ID ranges.
    If your id is not listed, go to the class with the right id range and mention to your tutor that your id is missed out.

    The four tutors are Zaid Alzobaidi, Masoud Koleini, Chuangjie Xu and Maxim Strygin, who will initially be allocated to groups as shown. (We may rotate them later.)

    Make sure you know which group you are in (1, 2, 3 or 4) and which room your exercise class is in.
    Each group has a different pigeonhole for returning homework; there is a fifth pigeonhole for all stretcher exercises.

    Group 1
    Students: -- 1066958
    Tutor: Zaid Alzobaidi
    Exercise Classes: LG33, Learning Centre (Building R28)

    Group 2
    Students: 1066959 -- 1089139
    Tutor: Masoud Koleini
    Exercise Classes: LG34, Learning Centre (Building R28)

    Group 3
    Students: 1089140 -- 1105303
    Tutor: Chuangjie Xu
    Exercise Classes: UG40, Computer Science

    Group 4
    Students: 1105304 --
    Tutor: Maxim Strygin
    Exercise Classes: LT2, Sport Ex (Building Y14)

    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!

    Note that the 2012 exam is in a different format from previous years. You are asked to attempt 3 questions out of 4, each being worth 34 marks. (Thus these total to 102, but will be capped at 100.)

    Here is what each of the four questions will cover:

    1. regular languages and finite automata
    2. context free grammars and pushdown automata
    3. Turing machines and complexity
    4. decidability and the lambda-calculus

    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.

    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.