Search programme

​Use the search function to search amongst programmes at Chalmers. The study programme and the study programme syllabus relating to your studies are generally from the academic year you began your studies.

Syllabus for

Academic year
TDA181 - Models of computation
 
Owner: TDATA
4,0 Credits (ECTS 6)
Grading: TH - Five, Four, Three, Not passed
Level: A
Department: 37 - COMPUTER SCIENCE AND ENGINEERING


Teaching language: Swedish

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 No Sp
0104 Examination 4,0 c Grading: TH   4,0 c   19 Oct 2005 am V,  11 Jan 2006 pm V,  Contact examiner

In programs

TDATA COMPUTER SCIENCE AND ENGINEERING - Computer Languages, Year 4 (compulsory)
TDATA COMPUTER SCIENCE AND ENGINEERING, Year 3 (compulsory)

Examiner:

Professor  Bengt Nordström


Replaces

TDA180   Foundations of computation


Eligibility:

For single subject courses within Chalmers programmes the same eligibility requirements apply, as to the programme(s) that the course is part of.

Course specific prerequisites

n/a

Aim

n/a

Content

In this course, we study the concepts of program, programming language and computation from a more general and mathematical point of view than in the introductory programming courses. Among other things, we study several so called models of computation. These can be seen as simplified programming languages that still contain a kernel of constructions necessary to get full expressive power. Examples of models of computation are the lambda-calculus, which is the basis of any functional programming language, and Turing machines, a very simple (theoretical) computer defined in the 30's by the mathematician Alan Turing. We discuss the limitations of the expressive power of programming languages - for example Turing's result that there is no computable solution of the so called halting problem. The course also contains an introduction to techniques for defining the syntax and semantics of programming languages in a precise way. More concretely, the different subjects we will study in the course are the following:

* Basic mathematical concepts:
o Sets;
o Mathematical induction;
o Relations;
o Functions;
o Enumerable and countable sets;
* Models of computation:
o (Automata and finite state machines;)
o Lambda-calculus;
o (Primitive) Recursive functions;
o Turing machines;
o Some other model of computation; options are X, PCF, P,...
* Computability: Are there any problems that no computer can solve ?

Organisation

There will be around 14 lectures and 7 exercise classes. Depending on the situation, some teaching could be held in small groups.

Literature

The homepage of the course. Lecture notes.
Kent Peterson: Beräkningsbarhet för dataloger: Från lambda till P, Bokförlaget AQUILA 1988

Examination

Weekly assingments and written exam.


Page manager Published: Mon 28 Nov 2016.