modules

It is popularly supposed that there is no limit to the power of computers to perform any task, so long as it is sufficiently well defined, and to do so quickly and efficiently. In fact this is not so, and it can be proved mathematically that there are well-defined computational tasks which cannot, in principle, be performed by computers as we know them; and other tasks which, while they can be performed, cannot be completed in a feasible amount of time. This module will introduce you to the Turing Machine model of computation which underpins the fundamental theories of computability (concerned with what can be computed at all) and complexity (concerned with how efficiently things which can be computed can be computed). These theories will be introduced in a precise and formal way, and the main results and theorems will be stated and proven. Pre-requisites: ECM1414 , ECM2418

_{Please note that all modules are subject to change, please get in touch if you have any questions about this module.}