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
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

TKITE SOFTWARE ENGINEERING, Year 3 (elective)
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 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.

Page manager Published: Mon 28 Nov 2016.