Module Title  Models of Computation 
School  Computer Science 
Department  Computer Science 
Module Code  06 05934 
Module Lead  Dr P B Levy 
Level  Intermediate Level 
Credits  10 
Semester  Semester 2 
Prerequisites 
Introduction to Mathematics for Computer Science  (06 20415)
LC Foundations of Computer Science  (06 22754)

Corequisites 

Restrictions  Prerequisites: 0618187 Foundations of Computer Science and 0620415 Introduction to Mathematics for Computer Science (or equivalent or Mathematics at A Level)

Contact Hours 
Lecture23 hours
Seminar0 hours
Tutorial0 hours
Project supervision0 hours
Demonstration0 hours
Practical Classes and workshops11 hours
Supervised time in studio/workshop0 hours
Fieldwork0 hours
External Visits0 hours
Work based learning0 hours
Guided independent study0 hours
Placement0 hours
Year Abroad0 hours

Exclusions  none 
Description  The course will introduce various automata theoretic models of computation and discuss their practical and theoretical significance. Finite automata, grammars and stack automata and Turing machines will be introduced. The fundamental ideas of (non)computability and complexity will be presented. There will also be a section on the Lambda Calculus and its connection with Functional Programming. 
Learning Outcomes  On completion of this module the student will be able to:  Explain the basics of automata theory, formal language theory, computability theory, complexity theory and lambda calculus;
 Explain noncomputability and nondecidability issues;
 Describe and use the connection between automata and languages; Explain and use lambda calculus as a theory of functional programming;
 Explain the connection between theory and applications.

Assessment 
0593401 : Examination : Exam (Centrally Timetabled)  Written Unseen (80%)
0593402 : Continuous Assessment : Coursework (20%)

Assessment Methods & Exceptions  1.5 hr written examination 80%, continuous assessment 20%. Resit available, 1.5hr examination (100%) 
Other  none 
Reading List 
