06 05934 Models of Computation

Volker Sorge 10 credits in Semester 2


The lectures are on Mondays, 9:00-11:00 in UG04, Learning Centre (Building R28 on the Campus Map)


We have published the solution to exercise in gzipped PostScript or pdf to help you with homework exercise 27.

I have issued an addendum for handout 5, with the Turing machine that accepts words of the form a2n, ≱0. Please pick it up here in gzipped PostScript or pdf.

There have been some mistake in the solutions to exercise 2, that were handed out in class today. Please either see the Errata or download the updated version here

Rooms and groups for the exercise classes will be announced Monday afternoon! Please have a look at the webpage before going to class on Tuesday.

Exercise Classes

Exercise classes are Tuesdays, 2:00-2:50pm. Exercises will be conducted in groups and you are expected to go to the group you are assigned to every week and hand in your homework with the respective tutor. Please check the links below to find your group. Note, that tutors have the right to reject work if you are in the wrong class!

Should your ID number not be on any of the lists, please email me. For the first exercise, please go to either of the groups and tell the tutor.

Group 1UG40, Computer ScienceZaid Al-Zobaidi / Aybek Mukhamedov
Group 2UG04, Learning CentreOlaf Klinke
Group 3UG05, Learning CentreOlufunmilola Onolaja

Information about the tutorials
20% continuous assessment: Every handout will contain Quickies, Classroom Exercises and Homework Exercises. The classroom 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. Quickies are small exercises best done shortly after the lecture to experiment with the new concepts. They will not all be assessed. Those that are assessed should be handed in to your tutor at the exercise class. Homework must be handed in through one of the departmental pigeon holes on the Ground Floor (next to the General Office). They are due Mondays, 9am. 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.

Clearly write your registration numbers on each sheet of your submission. No registration numbers -- no points. Do not write your names on your submission. Submissions with names will be marked but not returned. When handing in you homework exercises on Monday morning please refrain from attaching cover sheets. Just drop it in the right pigeon hole. Please observe that there is a separate pigeon hole for the stretcher exercises!

Marks will be assigned on the basis of your performance in both classroom and homework exercises. Marks will be made available on this webpage and through the School Information System.


If you have any questions, problems, or comments, please email me or come and see me during my office hours Monday 11-12am after the lecture. To see me outside these office hours, please email me and suggest some times, which are compatible with my timetable.

When emailing, please observe that you can expect the fastest response, when your email is short and in plain ASCII. If you have to send attachments, please make sure they are in some open standard format. In particular, do NOT send MS word files. Why? See here.

Recommended Books

Title Author(s) Publisher Comments
Introduction to the Theory of Computation, 2nd Edition Sipser PWS Publishing, 2005 Further Reading
Computers Ltd: What they really can't do Harel Oxford University Press, 2003 Further Reading
Introduction to Languages and the Theory of Computation Martin McGraw-Hill Further Reading
Computability and Complexity: From a Programming Perspective Jones MIT Press Further Reading
An Introduction to Functional Programming through Lambda Calculus Michaelson Addison-Wesley Further Reading

Handouts and Worksheets

It is planned to make the handouts for the lectures and the worksheets available on-line after they have been handed out in the lectures. Please DO NOT PRINT THEM OUT. First check for spare and reference copies which can be found in the School's library. DO NOT WASTE PRINTER RESOURCES.

Week Topic Handout Solutions
0 General Information gzipped PostScript, pdf  
1 Regular Expressions and Finite Automata gzipped PostScript, pdf gzipped PostScript, pdf
2 Regular Languages
Exercise 3
gzipped PostScript, pdf
gzipped PostScript, pdf
gzipped PostScript, pdf
gzipped PostScript, pdf
3 Context Free Grammars and Pushdown Automata gzipped PostScript, pdf gzipped PostScript, pdf
4 Turing Machines gzipped PostScript, pdf gzipped PostScript, pdf
5 Church's Thesis
gzipped PostScript, pdf
gzipped PostScript, pdf
Solution 26ps.gz, pdf
gzipped PostScript, pdf
6 The Halting Problem gzipped PostScript, pdf gzipped PostScript, pdf
7 Undecidability gzipped PostScript, pdf gzipped PostScript, pdf
8 Complexity gzipped PostScript, pdf gzipped PostScript, pdf
9 NP Completeness gzipped PostScript, pdf gzipped PostScript, pdf
10 Lambda Calculus gzipped PostScript, pdf gzipped PostScript, pdf
11 Review Suggestions gzipped PostScript, pdf  

Errata can be found here.

Maintained by: Volker Sorge, School of Computer Science, The University of Birmingham
Last modified: Wed Apr 15 17:24:12 BST 2009