Messages

Here is my solution of the exam from 2009 .

The final ordinary lecture took place today. I will solve the exam from 2009 Friday 3rd of December 1.15 pm in our usual room. Note the time: 13:15.

Solutions of past exams:

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

A link to the solution of the exam from 2009 will appear soon (but after I have solved the exam in class).

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.

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)

Here is a compendium I wrote a few years ago. In Chapter 1 and Chapter 2 you find some introductory material on primitive recursive function. This may be useful additional reading to those who find Lewis & Papadimitrious book hard to read.

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 .

Turing machine built out of Legos.

I have now registered your mandatory assignments in the university's database. Each and one of you should check that you are correctly registered (and thus enrolled for the final exam).

I will start to lecture from Lewis's and Papadimitriou's book Wednesday 10.

Soon 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.

The lecture Friday 29 is canceled due to a PhD defense.

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 22.

I have started to lecture Chapter 3 in Leary's book. 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.

Our student representative is Eivind (eivinded 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.

Good news: The legal matters are settled, and Leary's book will be available in Akademia very soon.

Due to copyright restrictions and various legal matters, Leary's book might not be available in the book store for a while. Please try to get hold of a copy of the book in some way or another. There should be quite a few copies around since we have been using the book for six or seven years. Try to get in touch with previous students of the course and ask if they can help you.

All the lectures are moved to Room B62 in Niels Henrik Abels hus ("The Math Building").

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.