Search programme

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

​​​

Syllabus for

Academic year
TDA182 - Models of computation
 
Owner: TKDAT
5,0 Credits (ECTS 7,5)
Grading: TH - Five, Four, Three, Not passed
Level: C
Department: 37 - COMPUTER SCIENCE AND ENGINEERING


Teaching language: Swedish

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 No Sp
0106 Examination 5,0 c Grading: TH   5,0 c   01 Jun 2007 am M,  Contact examiner
0206 Written and oral assignments 0,0 c Grading: UG   0,0 c    

In programs

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

Examiner:



Replaces

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

The course presupposes Programming languages or similar and an understanding of set theory and logic paired with experience with a functional language.

Aim

Here we offer an introduction ta a number of basic concepts in computing.

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

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: Thu 03 Nov 2022.