# Theory of Computation (H) COMPSCI4072

**Academic Session:**2019-20**School:**School of Computing Science**Credits:**10**Level:**Level 4 (SCQF level 10)**Typically Offered:**Semester 1**Available to Visiting Students:**Yes**Available to Erasmus Students:**Yes

#### Short Description

This course covers the theory of sequential, concurrent and quantum computation. The main topics are: formal language theory and the connection to automata; lambda calculus as a foundation for functional computation; pi calculus as a foundation for concurrent computation; the theory of operational semantics and type systems; principles of quantum computation.

#### Timetable

2 hours of lecture time and 1 hour of tutorial or practical work per week

#### Requirements of Entry

Algorithmics I (H) (or equivalent)

#### Excluded Courses

None

#### Co-requisites

None

#### Assessment

80% for the end of year exam

20% for assessed coursework, which is likely to be separated into two or three smaller assignments

The assessed coursework will assess ILOs 4, 7 and 10 as well as touching on other ILOs.

The exam will assess ILOs 1, 2, 3, 5, 6, 8 and 9.

**Main Assessment In:** April/May

**Are reassessment opportunities available for all summative assessments?** No

Reassessments are normally available for all courses, except those which contribute to the Honours classification. For non-Honours courses, students are offered reassessment in all or any of the components of assessment if the satisfactory (threshold) grade for the overall course is not achieved at the first attempt. This is normally grade D3 for undergraduate students and grade C3 for postgraduate students. Exceptionally it may not be possible to offer reassessment of some coursework items, in which case the mark achieved at the first attempt will be counted towards the final course grade. Any such exceptions for this course are described below.

The nature of the coursework is such that it takes a significant number of days to produce it and this effort is infeasible for supporting the re-doing of such coursework over the summer.

#### Course Aims

The aim of the course is to show how several models of computation can be formally defined in order to give a rigorous foundation for sequential, concurrent and quantum programming paradigms.

#### Intended Learning Outcomes of Course

By the end of this course students will be able to:

1. Explain the connection between formal languages and automata in terms of the Chomsky hierarchy;

2. Evaluate expressions in lambda calculus according to the definition of the reduction relation;

3. Determine whether or not expressions in lambda calculus are typable in the simple type system;

4. Implement lambda calculus expressions in a functional language such as Haskell or ML, or the functional fragment of Python;

5. Execute pi calculus processes according to the definition of the reduction relation, and determine bisimulation relationships between processes;

6. Determine whether or not processes in pi calculus are typable in the simple type system;

7. Implement pi calculus processes in a simulation environment or in an appropriate fragment of the Go programming language;

8. Explain the principles of quantum computation and the characteristics that distinguish it from classical computation;

9. Calculate the effect of quantum protocols and algorithms according to the laws of Hilbert spaces;

10. Implement and analyse quantum protocols and algorithms in a suitable simulation environment.

#### Minimum Requirement for Award of Credits

Students must submit at least 75% by weight of the components (including examinations) of the course's summative assessment.