Search course

Use the search function to find more information about the study programmes and courses available at Chalmers. When there is a course homepage, a house symbol is shown that leads to this page.

Graduate courses

Departments' graduate courses for PhD-students.

​​​​
​​

Syllabus for

Academic year
DAT415 - Computability  
Beräkningsbarhet
 
Syllabus adopted 2019-02-07 by Head of Programme (or corresponding)
Owner: MPALG
7,5 Credits
Grading: TH - Five, Four, Three, Fail
Education cycle: Second-cycle
Major subject: Computer Science and Engineering, Information Technology
Department: 37 - COMPUTER SCIENCE AND ENGINEERING


Teaching language: English
Application code: 02129
Open for exchange students: Yes
Block schedule: A

Module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 Summer course No Sp
0119 Examination 4,5 c Grading: TH   4,5 c   15 Jan 2020 am M   08 Apr 2020 am DIST  
0219 Written and oral assignments 3,0 c Grading: UG   3,0 c    

In programs

MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 1 (compulsory elective)
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 1 (elective)
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 2 (elective)

Examiner:

Nils Anders Danielsson

  Go to Course Homepage

Replaces

TDA181   Models of computation TDA182   Models of computation TDA183   Models of computation TDA184   Models of computation


Eligibility:


In order to be eligible for a second cycle course the applicant needs to fulfil the general and specific entry requirements of the programme that owns the course. (If the second cycle course is owned by a first cycle programme, second cycle entry requirements apply.)
Exemption from the eligibility requirement: Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling these requirements.

Course specific prerequisites

7.5 credits discrete mathematics (for instance TMV200 or TMV210).
7.5 credits functional programming (for instance TDA452 or TDA555).

Aim

This course is about the concept of "computation": how it can be modelled, and what its limits are.

Learning outcomes (after completion of the course the student should be able to)

After completion of the course, the student should be able to

  • 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,
  • 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,
  • analyse programs belonging to some models of computation, and
  • manipulate and analyse models of computation.

Content

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.

Organisation

Lectures and exercise sessions.

Literature

Course literature will be announced no later than 8 weeks prior to the start of the course.

Examination including compulsory elements

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


Page manager Published: Thu 04 Feb 2021.