Syllabus for |
|
| TDA183 - Models of computation |
| |
| Syllabus adopted 2015-02-12 by Head of Programme (or corresponding) |
| Owner: MPALG |
|
|
7,5 Credits |
| Grading: TH - Five, Four, Three, Not passed |
| Education cycle: Second-cycle |
|
Major subject: Computer Science and Engineering, Information Technology
|
|
Department: 37 - COMPUTER SCIENCE AND ENGINEERING
|
Teaching language: English
Open for exchange students
Block schedule:
A
| Course module |
|
Credit distribution |
|
Examination dates |
|
Sp1 |
Sp2 |
Sp3 |
Sp4 |
Summer course |
No Sp |
| 0108 |
Examination |
7,5 c |
Grading: TH |
|
|
7,5 c
|
|
|
|
|
|
13 Jan 2016 am M, |
07 Apr 2016 pm M |
In programs
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 1 (elective)
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 2 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (elective)
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)
Examiner:
Professor
Bengt Nordström
Replaces
TDA181
Models of computation TDA182
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
Basic knowledge in logic and functional programming. This knowledge can be obtained from the courses DAT060 Logic in computer science and TDA452 Functional programming given at Chalmers or from courses with similar content.
Aim
The aim of the course is to give a solid foundation on various models of computation. One of the main problem to be studied is the difference between similar concepts (like sets/types, functions/programs) in Mathematics and Programming. In order to see the unity of Mathematics and Computer Science it is necessary to have a good understanding of the basic concepts. The student will learn to see a program and a programming language as a mathematical object and study these using mathematical methods.
Learning outcomes (after completion of the course the student should be able to)
- understand the difference between a program and a function.
- understand abstract and concrete syntax
- explain Church's thesis
- explain primitive recursive function
- explain why a set is enumerable or not
- give examples of problems which are not computable
- represent inductively defined sets in various computational models
- present different computational models
- give examples how to express programs in different models
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:Sets;Mathematical induction;Relations; Functions; Enumerable and countable sets;
Models of computation:(Automata and finite state machines;) Lambda-calculus; (Primitive) Recursive functions; Turing machines;
Some other model of computation; options are X, PCF, P,...
Computability: Are there any problems that no computer can solve ?
Organisation
Lectures and exercises.
Literature
The homepage of the course. Lecture notes.
Examination
Home assignments, weekly exercises,
Written exam.