Lecture Notes

The notes will be very sparse; I will only put in them definitions and the like (and maybe some worked, tedious exercises). The rest of the matter will be discussed on the blackboard; these notes are just a mean to save some writing (and so some time).

  1. Alphabets and languages (handout and overhead presentation): This set includes some mathematical preliminaries and a discussion on the math of strings of symbols (which will be our bread and butter for the remainder of the course). This covers Chapter 1 from the textbook; in this particular instance it is probably not necessary to read the chapter in advance (but it will certainly not hurt if you do).

  2. Finite automata (handout and overhead presentation): These lectures cover Chapter 2. Most of you have seen most of it in earlier courses so I expect to go through this chapter fairly quickly; make sure you read in advance ask questions as needed, otherwise the chapter will be finished before you know it.

  3. Context-free languages (handout and overhead presentation): We now cover Chapter 3 (except Sections 3.6 and 3.7). Said sections (3.6 and 3.7) are covered however briefly in our talk about deterministic context-free languages (handout and overhead presentation).

  4. Turing machines (handout and overhead presentation): These lectures cover most of Chapter 4. We now reach a general model of computation. For the time being we define the model (and a few variants); we will see what we can do with this model later in the course.

  5. Computability (handout and overhead presentation): Includes a discussion on the universal Turing machine and the Church-Turing thesis. This is all covered in Chapter 7 (with Section 5.7 covered to a lesser degree).

  6. Complexity (handout and overhead presentation) is the a substantial section of this course. It covers Chapters 6 and 7 (less Section 7.4).

  7. We conclude with a brief presentation of Other Turing-complete models (handout and overhead presentation)

Lecture recording

In most cases there are two videos for each recorded lecture, one featuring the camera feed and the other featuring a capture of the front desk screen. The audio track is the same for both videos. There aren't too many interesting things happening on the screen, so you should probably start with the camera stream combined with a separate view of the respective PDF lecture notes. Alternatively, you can to run both streams simultaneously (one of them muted).