Newer
Older
---
title: Models of Computation
parent_menu: Teaching
menu_order: 5
This is a 2nd year MEng compulsory course at the [Department of Computing](http://www.imperial.ac.uk/computing), [Imperial College London](http://www.imperial.ac.uk).
The course focuses on teaching students the fundamental skills involved in dealing with abstract systems and constructing proofs, through both teaching and exercises.
#### Description of the Course
This course provides a whirlwind tour of some of the key concepts in theoretical computer science.
In particular, we will study formal descriptions (models) of computational behaviour.
#### Course Outline
The course comprises two hours a week for seven weeks.
#### General Information for 2018 autumn term
Time: Wednesdays: 9am - 11am, Room 308.
Assesed coursework 1: published Wed 31st Oct, 9 AM / deadline for submission Fri 9th Nov, 4 PM
Assesed coursework 2: published Wed 28th Nov, 9 AM / deadline for submission Tue 11th Dec, 4 PM
Tutorials: Tutorial exercises will be posted online (here and on CATE) before the tutorial each week, printed copies will also be available. Tutorial solutions will be published online before the next week's tutorial.
Recommended Reading:
H.R. Nielson and F. Nielson (1999). Semantics with Applications: A Formal Introduction, originally published in 1992 by John Wiley and Sons.
[Revised edition](http://www.doc.ic.ac.uk/~pg/Computation/book.pdf)
G. Winskel (1993). The Formal Semantics of Programming Languages, MIT Press.
This is an excellent introduction to both the operational and denotational semantics of programming languages.
M. Hennessy (1990). The Semantics of Programming Languages, Wiley.
The book is subtitled 'An Elementary Introduction using Structural Operational Semantics', and provides a leisurely introduction to some of the topics in this course.
[Revised edition](https://www.cs.tcd.ie/matthew.hennessy/splexternal2015/resources/sembookWiley.pdf)
J.E. Hopcroft, R. Motwani and J.D. Ullman (2001). Introduction to Automata Theory, Languages and Computation, 2nd edition, Addison-Wesley.
J.R. Hindley and J.P. Seldin (2008). Lambda Calculus and Combinators, an Introduction, 2nd edition, Cambridge University Press.
F. Cardone and J.R. Hindley (2006). [History of Lambda-calculus and Combinatory Logic.](http://www.users.waitrose.com/~hindley/SomePapers_PDFs/2006CarHin,HistlamRp.pdf)
N,J. Cutland (1980). Computability. An Introduction to Recursive Function Theory, Cambridge University Press.
M.D. Davis, R. Sigal and E.J. Wyuker. (1994). Computability, Complexity and Languages, 2nd edition, Academic Press.
T.A. Sudkamp (1995). Languages and Machines, 2nd edition, Addison-Wesley.
Other Recommendations: [Logicomix](http://www.logicomix.com/en/): the graphic novel Logicomix was inspired by the epic story of the quest for the Foundations of Mathematics...
[Turing](http://www.amazon.com/Turing-Novel-Computation-Christos-Papadimitriou/dp/0262162180) (A Novel about Computation), Christos Papadimitriou, Berkeley.
[Scooping the Loop Snooper](http://www.cl.cam.ac.uk/teaching/0910/CompTheory/scooping.pdf)(© Mathematical Association of America), a poetic proof of the undecidability of the halting problem in the style of Dr Seuss by Geoffrey K. Pullum.
A real [Turing machine.](http://robotzeitgeist.com/2010/03/model-turing-machine.html)
[LEGO Turing Machine]. (https://www.youtube.com/watch?v=cYw2ewoO6c4)