Course syllabus adopted 2021-02-26 by Head of Programme (or corresponding).
Overview
- Swedish nameBeräkningsbarhet
- CodeDAT415
- Credits7.5 Credits
- OwnerMPALG
- Education cycleSecond-cycle
- Main field of studyComputer Science and Engineering, Software Engineering
- DepartmentCOMPUTER SCIENCE AND ENGINEERING
- GradingTH - Pass with distinction (5), Pass with credit (4), Pass (3), Fail
Course round 1
- Teaching language English
- Application code 02114
- Block schedule
- Open for exchange studentsYes
Credit distribution
Module | Sp1 | Sp2 | Sp3 | Sp4 | Summer | Not Sp | Examination dates |
|---|---|---|---|---|---|---|---|
| 0119 Examination 4.5 c Grading: TH | 4.5 c |
| |||||
| 0219 Written and oral assignments 3 c Grading: UG | 3 c |
In programmes
- MPALG - COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 1 (compulsory elective)
- MPALG - COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 2 (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- Associate Professor, Computing Science, Computer Science and Engineering
Eligibility
General entry requirements for Master's level (second cycle)Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.
Specific entry requirements
English 6 (or by other approved means with the equivalent proficiency level)Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.
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.
The course examiner may assess individual students in other ways than what is stated above if there are special reasons for doing so, for example if a student has a decision from Chalmers on educational support due to disability.