Models of Computation - TDA 183 - DIT 310
Computing Science, Chalmers, Univ of Göteborg
Basic info about the course
Lecturer: Bengt Nordström
Google group: Announcements and discussions. Join it!
Chalmers official info page: (prerequisites, exam date, learning outcome, etc)
Link to the fire system (the system we use for the weekly assignments)
In the same way as the work of ordinary engineers is based on Physics and other sciences the work of a software engineer is based on a solid mathematical foundation. A model of computation is part of such a foundation.
Some examples of computation models are
Lambda calculus which was developed by Alonzo Church in the 1930s
Turing machine developed by Alan Turing, also around 1930.
Markov algorithms developed by Andrey Markov (not to be confused with his father Andrey who among other things developed the theory of Markov processes).
General recursive functions developed by Gödel in 1934.
Primitive recursive functions
We will discuss some inherent limitations in these models, for instance Turing's result that there is no program which solves the halting problem (does a given program terminate or not?). Another important part of the course is to show how syntax and semantics of programming languages can be expressed in a precise way.
A computational model can be seen as a precisely defined simplified programming language. The reason it is simplified is that this is the only way we can study it it as a mathematical object. This is in the same tradition as in Physics where we give mathematical models of our physical reality. They use strings with no mass, particles with mass and no volume etc. These completely unrealistic assumptions are absolutely necessary if we want to have a deeper understanding of our physical reality.
In this course we study the fundamental concepts like program, computation and programming language from a more foundational and mathematical view. If you want to do this, it is impossible to use an existing programming language since they are too complex. A precise description of languages like C, Java or Haskell requires several hundred pages! Consider for instance the fact that usual arithmetical operations are not valid (for instance n - n is not always 0, not even for integers). Other problematic features are parallel execution and interrupts.
Goals
The introductory courses in programming is about programming in a given programming language. You learn a number of syntactic conventions and learn how to program by solving some concrete problems.
2 - 6 Nov: Algorithms, Functions and Counting Infinite Sets.
We will start the course by every student filling in this quiz. It is used to find out the background knowledge of the students.
Some questions:
How old is the concept of algorithms?
Is a function the same as an algorithm?
Are there more functions from N to N then algorithms?
What does it mean that two infinite sets have the same number of elements?
What is a computable function?
What is Church's thesis?
Reading:
Bengt Nordström: Are all functions computable?
Tony Hoare and DCS Allison: Incomputability.
Extra Reading (in Swedish):
Kent Petersson: Beräkningsbarhet för dataloger. Från lambda till P. This Swedish book was used earlier for a predecessor of this course.
Exercises:
The exercises (which can be found here) will be discussed on Wednesday. You will get points towards your examination if you are prepared to present your solutions to the class. Please submit them before 10:00 on Wednesday.
Assignments:
This assignment has to be handed in before Monday. It is easy!
9 - 13 Nov: Mathematical Foundations
In order to give examples of mathematical models we have to have certain mathematical concepts clear. The most important of these are concepts like functions and inductively defined sets. Also properties of functions, like enumerable, partial, total functions, surjective, injective, etc.
The mathematical concept of function is very different from the function concept in programming languages. The latter (where we see a function as a method to compute a result from an argument) is very close to how functions were understood in mathematics before the 20'th century.With the advent of Set Theory a more abstract notion was introduced. It is important to have a good understanding of this difference.
In a similar way, the concept of a data type in programming languages is very close to the concept of set in mathematics. In this course we will use inductively defined sets, which is even more similar to data types.
Reading:
B. Nordström: Some mathematical preliminaries
B. Nordström: Enumerable sets and Hilbert's hotel.
Questions:
Is the set of natural numbers enumerable?
Is the set of total functions from N to Bool enumerable?
Is the set of lists of rational numbers enumerable?
How do you give an inductive definition of the set of lists, where the elements are in a set A?
How does an inductive definition of a set give a method to define a function from that set (primitive recursion)?
How does it give a proof principle for proving properties about elements in the set (structural induction)?
Exercises:
These exercises will be discussed on Wednesday. You will get points towards the final examination if you are willing to present your solution to the class.
Assignments:
These must be handed in before Sunday midnight.
16 - 20 Nov: Lambda calculus
Questions:
What is the value of (\x.((((x x)x)x)l)l) (\y.(\z.y(y z)))?
What is the syntax of lambda calculus?
What does it mean for a variable to be free (bound) in an expression?
What is beta-reduction?
What is a redex?
How do you reduce (\y x. y)(\y.x y)?
What is a normal form?
Does all expression have a normal form?
What are the two most common evaluation strategies?
Give an inductive definition of some evaluation strategies!
Can different reduction strategies lead to different results?
What is a combinator?
What is a fixpoint combinator?
How do you express recursion?
How do you represent elements in inductively defined sets in lambda calculus?
What does it mean that a function is computable in lambda calculus?
Reading:
John Harrrison: Lambda calculus
John Harrrison: Lambda calculus as a programming language
Extra reading: Ana Bove's slides
Extra reading: Panangaden's lecture notes.
Exercises:
These will be discussed on Wednesday. You will get points towards your examination if you are prepared to present your solutions to the class. Please report before 10:00 on Wednesday.
Assignments:
These must be handed in before Sunday midnight.
23 - 27 Nov: Primitive recursive functions
Summary:
Earlier we saw how to define an operator which expresses the scheme for primitive recursion over natural numbers. One of the earliest attempts to give a mathematical models of all computable functions was made in 1935 by Stephen Kleene who introduced the set of primitive recursive functions. The functions in this class are computable, but there are computable functions outside the class. We will explain the abstract and concrete syntax and an informal and formal semantics of it. We will give both an operational semantics and a denotational semantics.
This model of computation has not only historical interest. The programs are expressed without variables, this kind of representation has been used to implement functional programming languages. The idea of using an operator of primitive recursion instead of allowing general recursive function definitions has been carried over to many programming logics.
Reading:
Bengt Nordström: The primitive recursive functions
Exercises:
These will be discussed on Wednesday. You will get points towards your examination if you are prepared to present your solutions to the class.
Assignments:
These must be handed in before Sunday midnight.
30 Nov - 4 Dec: X: syntax and semantics
Questions:
What is the concrete syntax of X?
What is the abstract syntax of X?
What is the informal semantics?
What is the formal semantics?
Reading:
The language X
Exercises:
These will be discussed on Wednesday. You will get points towards your examination if you are prepared to present your solutions to the class. Please report before 10:00 on Wednesday.
Assignments:
These must be handed in before Sunday midnight.
7 - 11 Dec: X: programming and coding
Questions:
How is patternmatching expressed?
How are recursive definitions expressed?
How is substitution defined?
How is an element in an inductively defined set coded?
How is a program in X coded in X?
What is a self evaluator?
What does it mean that a mathematical function is X-computable?
Is the intensional halting problem X-computable?
Reading:
The language X (same as last week)
Exercises:
These will be discussed on Wednesday. You will get points towards your examination if you are prepared to present your solutions to the class. Please report before 10:00 on Wednesday.
Assignments:
These must be handed in before Sunday midnight.
14 - 18 Dec: Turing machines
Here is a wonderful poetic proof of the halting problem, Scooping the Loop Snooper, written by Geoffrey Pullum.
Some questions:
What is a Turing machine? Give some alternative formulations!
What does it mean that a function is Turing-computable?
How do you describe the operational semantics of a Turing machine?
How do you prove that the halting problem for Turing machines is uncomputable?
Reading:
Description of a Turing Machine for a Functional Programmer
There are a number of descriptions of Turing machines on the web:
Turing Machines. (Stanford Encyclopedia of Philosophy) This is the one I recommend.
Turing Machines. (Wikipedia), This is also good.
Exercises:
On Wednesday we will first discuss the exercises and assignments which we have had during the course. If you have some question about an old problem, don't hesitate to bring it up! It is only you who know what kind of questions you have. It is very difficult for me to guess what you have not understood yet.
The second part (after a short break) of the exercise session will be devoted to general questions about the lectures and the lecture notes. Here is a form to send in the questions.
There will be no points for filling in the form above.
Schedule
The scedule is given in the calendar above. The first lecture is on Monday 1 Nov. You can subscribe to this calendar to your ical calendar if you use this link or by clicking on the +google-button in the right hand lower corner of the calendar above.
Notice that the ordinary Chalmers calendar does not reflect the real schedule (to make a change in the official Chalmers calendar is like changing the direction of a supertanker. )
Lectures are usually on Mondays at 10.00 in EL43 in the EDIT house.
Discussion of exercises are usually on Wednesdays in EL43 at 13.15 -- 15.00. We can stay there until 17.00, in case we need the extra time.
The essential content in the course is presented on this home page and during the lectures.
The schedule can be changed during the term, this change will be announced on the google group and be visible in the calendar above.
Examination
You have to have 100 points in order to pass the course.
It is possible to get 200 points:
20 points for the exercises
40 points for the written assignments (5+6+7+7+7+8)
140 points for the written exam
The limits for the various grades are:
For Chalmers students: 3 = 100, 4 = 135, 5 = 160.
For University students: G = 100 and VG = 160.
The points for the exercises and the assignments are valid one year after the start of the course.
There are no compulsory parts of this course, you just have to collect 100 points to pass the course.
The time for the written examinations are: (as copied from Chalmers examination page, please check!!) 14 Jan at 8:30 (Hörsalsvägen) and 16 April at 14:00 (Johanneberg).
Exercises and weekly assignments
There is a number of weekly exercises which we are usually discussing in class on Wednesdays. If you have solved these and are willing to present your solutions to the class you will get some points towards the final examination (each session is worth 4 points). You have to report this electronically using the link on the home page at least three hours before the class on Wednesday.
We will also have weekly written assignments which is to be handed in electronically (no scanned handwritings please!) during the weekend. These will count up to additional 40 points ( = 5+6+7+7+7+8). Late assignments can be handed in before 8 o'clock on Monday, but there will be a 25 % deduction of the score. All assignments are to be handed in individually and you are not allowed to show your solutions to any other student. You are allowed to discuss the problems with other students, but you are not allowed to show your final solution to any other student. And you are not allowed to read solutions from other students. The assignments are part of the examination and any violation of these rules will be reported to the discipline committee of Chalmers. Here is a paper describing the policy of academic honesty at Chalmers.
There is a database with the collected exercise points here.
Assignments:
No assignments this week.