Messages

The solution for the exam from 2007 is extended. Moreover, some miss prints are corrected.

The solution of the exam from 2006 is corrected and extended. I have provided a solution of Problem 3 from 2006 (in English).

We will discuss the solution of the exam from 2007 on Monday.

Solutions of past exams:

• 2005 (Norwegian)
• 2006 (Norwegian/English)
• 2007 (English)

Here is the plan for the remaining lectures: We will also solve some exercises. Here are some candidates: ex. 1, 2, 3, 4, 5, 6, 9 and 10 at pp. 136-137. We will study previous exams: The exam from 2006 (MAT4600) and the exam from 2007 (MAT4600). Both exams are available in English.

I have now registered everyone who has completed the "oblig" for the final exam. Please, check on the Internett that everything is all right, follow this link

You need parts of the following textbook.

• Lewis & Papadimitriou: Elements of the Theory of Computation .(second edition)

You will need the following parts.

• From Chapter 4 (Turing Machines): Section 4.1, 4.2, 4.3 (pp. 179-209)and Section 4.7 (pp. 233-244).

• From Chapter 5 (Undecidability): Section 5.1, 5.2, 5.3 and 5.4 (pp. 245-257)

New exercise: ex. 3 at page 109.

We have finally received permission to make reprints of Leary's book, and a copy of the book is now available in the book store (Akademia). You have to ask the staff for the book as you will not find it in the shelves. (However, I suppose you all have acquired a copy by now.)

I have started to lecture Chapther 3. Exercises to be solved in the weeks to come : 3.2.1 (page 101): ex. 1, ex. 2, ex. 3, ex. 4, ex. 5, ex. 9. 3.3.1 (page 109): ex. 1,ex. 5, ex. 6, ex. 8 a,b,d, ex. 9, ex. 10, ex. 11.

The "oblig" (mandatory assignment) is now available. I have left some copies in my mailbox by the Reception Office. The deadline is October 15.

I have started to lecture Chapter 2. Exercises that might be solved in the weeks to come: 2.2.1 (page 55): ex. 1, ex. 4. 2.4.3 (page 62): ex. 4, ex. 5, ex. 6. 2.7.1 (page 76): ex. 4, ex. 5, ex. 6, ex. 7. 2.8.1 (page 81): ex. 2, ex. 4, ex. 5, ex. 6, ex. 5, ex. 8.

Everyone should have a copy of "Leary: A friendly introduction to mathematical logic". Please, do you best to acquire a copy of the book. Unfortunately, the book will not be available in the book store in the foreseeable future.

The next few weeks I will lecture the 1st chapter of Leary's book. The following exercises might be solved during the lectures: 1.3.1 (page 15): ex. 2, ex. 3. 1.4.1 (page 20): ex. 3, ex. 4, ex. 5. 1.6.1 (page 30): ex. 2, ex. 3, ex. 5. 1.7.1 (page 38): ex. 2, ex. 7. 1.8.1 (page 42): ex. 6. 1.9.1 (page 44): ex. 1, ex. 2, ex. 4.