Module 35393 (2020)
Module description - Theories of Computation
The Module Description is a strict subset of the Syllabus Page.
|Module Title||Theories of Computation|
|School||School of Computer Science|
|Member of Staff||Paul Levy Benedikt Ahrens Mian Muhammad Hamayun|
|Semester||Semester 2 - 20 credits|
Computers have been used to solve an astonishing range of different problems, but this does not mean that they can be used to solve all possible problems: some cannot be solved efficiently, and some cannot be solved at all. In this module, we will introduce a set of principles and techniques for formalising computation and computability to understand what problems can be solved, how efficiently they can be solved, and what problems cannot be solved. We will develop mathematical models of computations using ideas such as sutomata theory (including Turing machines), of formal languages using ideas such as regular expressions and grammars, and will conclude by considering the notions of non-computability and complexity.
On successful completion of this module, the student should be able to: