Syllabus for |
|
| 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.