CS103 – Machines, Languages & Computation

TIMETABLE TEACHING MATERIAL
Credits 20
Level SHE Level 1
Prerequisites Basic use of algebra, as might be gained by taking Standard Grade Mathematics or a similar course.
Availability Semesters 1 & 2
Elective Yes
Contact 44 lectures
Assessment 30% classwork, 70% written exam, with possibility of exam exemption
Lecturer Dr John LevineDr David Bevan

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:

  1. To understand the difference between computable and non-computable functions and to demonstrate that non-computable functions can exist.
  2. To understand the concept of a formal language for specifying structures and the concept of recursion in both grammatical rules and function specifications.
  3. To understand the concept of a rewriting system for symbolic manipulation and to produce derivations using such a system.
  4. To understand the propositional calculus as a set of symbolic rules, and to derive theorems in the propositional calculus using these rules.
  5. To understand the difference between tractable, intractable and undecidable problems and to understand what a decision procedure is.
  6. To understand the concept of an abstract machine for performing computation, with reference to finite state machines and Turing machines.

Syllabus

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Weekly Work Pattern

There are two lectures per week every week over both semesters. In between the two lectures, students spend around 4 hours per week on assigned reading from the class textbook (see below) and a weekly pen-and-paper exercise.

Assessment and Exemption

There are four class tests, two in each semester, each worth 7.5% of the overall class mark. Each class test contains questions which are closely connected to the content of the weekly exercises set in class. The remaining 70% of the mark for the class comes from a 2 hour degree examination, sat in the summer diet.

Students who achieve a pass (i.e. at least 40%) in all four of the class tests and an average of at least 60% over all four class tests will be exempted from the degree examination. The mark returned for a student who is exempt will be the average mark gained on the four class tests.

Resit

The resit for the class will take the form of a 2 hour examination in the same format as the original degree examination. The mark returned for the resit attempt will be based on the resit examination alone.

Indicative 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: 0140289208.