(or equivalent authorised by Director of Studies)
Aims: To introduce the capabilities of different kinds of machines, to explore the relationship between Turing machines and algorithms, and to explore the limitations of Turing computability. To introduce the Lambda calculus.
Learning Outcomes:
1.To appreciate the limitations of finite-state machines, and the availability of different possible standard formalisations of Turing machines;
2.To understand what can and cannot be computed using Turing machines, and the relationship between Turing machines and algorithms;
3.In the lambda calculus, students should be able to find normal forms, when these exist, using alpha and beta reduction.
Skills:
IT (T/F, A), Application of Number (T/F, A).
Content:
Languages and regular expressions. The basic properties of finite-state machines. Non-deterministic finite-state machines. What can and cannot be computed using finite-state machines. Turing Machines. Connecting standard Turing Machines together. Grammars, languages and the Chomsky classification. Introduction to Church's Thesis. Universal Turing Machines and limitations of Turing computability. Undecidability, the Halting Problem, reduction of one unsolvable problem to another. Lambda calculus. Alpha and Beta reduction. Confluence. Church-Rosser Theorem.
| |
Fax: +44 (0) 1225 386366