Teaching language: English
Open for exchange students: Yes
Block schedule:
A
Course module 

Credit distribution 

Examination dates 
Sp1 
Sp2 
Sp3 
Sp4 
Summer course 
No Sp 
0116 
Examination 
4,5c 
Grading: TH 


4,5c






16 Jan 2019 am M

25 Apr 2019 pm J 
0216 
Written and oral assignments 
3,0c 
Grading: UG 


3,0c







In programs
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 1 (elective)
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 2 (elective)
MPALG COMPUTER SCIENCE  ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 2 (elective)
MPALG COMPUTER SCIENCE  ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 1 (compulsory elective)
Examiner:
Nils Anders Danielsson
Replaces
TDA181
Models of computation
TDA182
Models of computation
TDA183
Models of computation
Go to Course Homepage
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 hec discrete mathematics (for instance TMV200 or TMV210). 7.5 hec functional programming (for instance TDA452 or TDA555).
Aim
This course is about the concept of "computation": how it can be modeled, 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 ChurchTuring 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 (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. 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 ChurchTuring 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
See the course web page.
Examination including compulsory elements
The course is examined by an individual written examination carried out in an examination hall and by individual written assignments.

