Beskjeder

Here is the solution of the exam from 2008.

We will meet 1 pm on Wednesday. You may ask questions, and we can discuss the exam from 2007.

The course curriculum is

• everything in Leary's book until the middle of page 186 (and nothing more)
• the parts of Lewis & Papadimitriou's book specified below.

We will study the exam from 2008 on Monday (November 30).

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 .

These exercises will be solved in class very soon.

Monday's lecture was canceled due to illness. I am getting better and there will probably be a lecture on Wednesday.

Solutions of past exams:

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

A link to the solution of the exam from 2008 will be given in late November (after I have solved the exam in class).

Monday 26: I will solve the mandatory assignment. Wednesday 28: I will start to lecture computability theory (Lewis and Papadimitriou).

Within a few weeks you will need parts of the 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)

Please inform me if it is hard to get hold of a copy.

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. 3, ex. 5, ex. 6, ex. 8 a,b,d, ex. 9, ex. 10, ex. 11.

There will be no ordinary lecture October 5, but I will be present in the lecture room a quarter past noon as usual such that the students can ask questions related to the mandatory assignment.

The "oblig" (mandatory assignment) is now available. I have left some copies in my mailbox at the 7th floor (Room 700). The deadline is October 12.

The student representatives are

• Tobias Vidarss?nn Langhoff (tobiasvl at ifi.uio.no)
• Anders Solli Sal (andersal at student.matnat.uio.no)

I have started to lecture Chapter 2 of Leary's book. 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". The book is available in the book store (Akademia).

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.