Computability

The course can be part of the following programmes:

1. Computer Science, Master's Programme (N2COS)
2. Computer Science, Bachelor's Programme (N1COS)

The course is a also a single-subject course at Gothenburg University.

To be eligible to the course, the student should have successfully completed 120 credits of studies in Computer Science or equivalent.

Specifically, the following courses are required, or equivalent:

• 7.5 credits in discrete mathematics (e.g., DIT980 Discrete Mathematics for Computer Scientists)
• 7.5 credits in functional programming (e.g., DIT143 Functional Programming or DIT440 Introduction to Functional Programming)

Applicants must prove knowledge of English: English 6/English level 2 or the equivalent level of an internationally recognized test, for example TOEFL, IELTS.

This course is about the concept of "computation": how it can be modelled, and what its limits are. To avoid unnecessary complexity one often chooses to study computation via simplified, but powerful, models. These models can for instance be simple programming
languages (like the -calculus), or idealised computers (like Turing machines). In the course several such models will be studied, both "imperative" and "functional".

One or more models will be used to explore the limits of computation: problems that cannot be solved (within the confines of a given model), and programs that can run arbitrary programs (modelled in a certain way).

The course also includes a discussion of the Church-Turing thesis, a hypothesis which states, roughly, that a function is computable in a certain intuitive sense only if it can be defined within one of several models of computation.

On successful completion of the course the student will be able to:

Knowledge and understanding

• define the notion of computable function,
• explain the Church-Turing thesis,
• explain the relationship between inductively defined sets, primitive recursion, and proofs by structural induction,

Competence and skills

• prove that sets are countable or uncountable, for instance by using diagonalisation,
• encode inductively defined sets in such a way that members of these sets can be used as inputs or outputs for programs in one or more models of computation,
• implement programs—in particular, interpreters—correctly in one or more models of computation,
• prove that functions are or are not computable in some models of computation,

Judgement and approach

• analyse programs belonging to some models of computation, and
• manipulate and analyse models of computation.

Lectures and exercise sessions.

Language of instruction: English

The course is examined by an individual written examination carried out in an examination hall, and by individual written assignments.

If a student who has been failed twice for the same examination element wishes to change examiner before the next examination session, such a request is to be granted unless there are specific reasons to the contrary (Chapter 6 Section 22 HF).

If a student has received a certificate of disability study support from the University of Gothenburg with a recommendation of adapted examination and/or adapted forms of assessment, an examiner may decide, if this is consistent with the course’s intended learning outcomes and provided that no unreasonable resources would be needed, to grant the student adapted examination and/or adapted forms of assessment.

If a course has been discontinued or undergone major changes, the student must be offered at least two examination sessions in addition to ordinary examination sessions. These sessions are to be spread over a period of at least one year but no more than two years after the course has been discontinued/changed. The same applies to placement and internship (VFU) except that this is restricted to only one further examination session.

If a student has been notified that they fulfil the requirements for being a student at Riksidrottsuniversitetet (RIU student), to combine elite sports activities with studies, the examiner is entitled to decide on adaptation of examinations if this is done in accordance with the Local rules regarding RIU students at the University of Gothenburg.

Sub-courses

1. Written hall examination, 4.5 credits
   Grading scale: Pass with distinction (5), Pass with credit (4), Pass (3) and Fail (U)
2. Assignments, 3 credits
   Grading scale: Pass (G) and Fail (U)

The grading scale comprises: Pass with distinction (5), Pass with credit (4), Pass (3) and Fail (U).

In this course one of the grades 5, 4, 3 and U is awarded. In order to get one of the grades 5, 4 or 3 one has to get the grade G on the sub-course Assignments, and a passing grade (5, 4 or 3) on the sub-course Written hall examination. In that case the grade on the course is the grade on the sub-course Written hall examination. In other cases the
grade on the course is U (fail).

The course is evaluated through meetings both during and after the course between teachers and student representatives. Further, an anonymous questionnaire is used to ensure written information. The outcome of the evaluations serves to improve the course by indication which parts could be added, improved, changed or removed.

The course is a joint course together with Chalmers.

The course replaces the course DIT312, 7.5 credits. The course cannot be included in a degree which contains DIT312. Neither can the course be included in a degree which is based on another degree in which the course DIT312 is included.