CS103 - Machines, Languages & Computation
| TIMETABLE | TEACHING MATERIAL |
| Credits | 20 |
| Level | 1 |
| Semester | Semester 1, Semester 2 |
| Availability | Can be chosen as an elective. |
| Prerequisites | Basic use of algebra, as might be gained by taking Standard Grade Mathematics or a similar course. |
| Learning Activities Breakdown | 40 lectures and 20 tutorials. There are two lectures and one tutorial per week every week over both semesters. In between the two lectures, students spend around 2-3 hours per week on a weekly pen-and-paper exercise. The exercises are discussed at the weekly tutorials, and some exercises will count towards the overall mark for the module. |
| Assessment | The module is assessed by four class tests, two in each semester. Each class test counts for 25% of the final mark. |
| Lecturer | John Levine, Radu Mardare |
Aims and Objectives
To help students to achieve a broad knowledge of the essence of computation and computational systems, as embodied by the notions of computable functions, formal languages and recursion, logic and computability and abstract machines.
Learning Outcomes
On completion of this class, a student should be able:
- To understand the difference between computable and non-computable functions and to demonstrate that non-computable functions can exist.
- To understand the concept of a formal language for specifying structures and the concept of recursion in both grammatical rules and function specifications.
- To understand the concept of a rewriting system for symbolic manipulation and to produce derivations using such a system.
- To understand the propositional calculus as a set of symbolic rules, and to derive theorems in the propositional calculus using these rules.
- To understand the difference between tractable, intractable and undecidable problems and to understand what a decision procedure is.
- To understand the concept of an abstract machine for performing computation, with reference to finite state machines and Turing machines.
Syllabus
- Computable and Non-Computable Functions: an introduction to the ideas of functions, computable functions, infinite sets of different cardinalities and the symbolic derivation of theorems, leading up to a proof of the existence of non-computable functions; an introduction to symbolic systems and the notion of theoremhood in such a system; the idea of lambda-calculus as a notation for computable functions; the relationship between computable functions and computer programs.
- Recursion and Languages: a first look at context-free grammars and the idea that finite grammatical rules can capture infinitely many strings through recursion; the idea that recursion can be used in functions and in logical rules and definitions; an introduction to formal languages and the specification of grammatical rules to capture the structure of a given language; recognising and understanding recursive definitions; proof by structural induction.
- Logic and Computability: introducing the propositional calculus as a set of symbolic rules and proving theorems in propositional calculus by natural deduction; lambda-calculus as a notation for proofs; the notions of soundness and completeness for a symbolic system; the idea of a decision procedure and a decision procedure for theoremhood in the propositional calculus; the three classes of problems: tractable, intractable and undecidable; the P=NP question.
- Abstract Machines: finite state machines as simple abstract models of computation with some examples; what finite state machines can’t do and an example; adding memory to a finite state machine to form a Turing machine; Turing machines as computable function boxes; the idea of the Universal Turing machine; the Church-Turing thesis: the limits of computational power; some examples of some undecidable problems.
Recommended Reading
This list is indicative only – the class lecturer may recommend alternative reading material. Please do not purchase any of the reading material listed below until you have confirmed with the class lecturer that it will be used for this class.
Gödel, Escher, Bach: an Eternal Golden Braid by Douglas R. Hofstadter. Penguin Books Ltd. ISBN: 0465026567.
Last updated: 2024-01-26 00:14:02