### Final Exam

December 11,2009

The final exam is Wednesday Dec 16 from 9am to 12 noon in room 2-135. You may not bring in any supplemental notes or aids.

The exam will be cumulative, covering material from class, the textbook readings, handouts, and problem sets. Solutions to all the problem sets (and to the extra practice questions) and all the handouts may be found on the handouts page.

If you have any questions, you can email them to me and/or email me for an appointment.

### Missing oracle and equals

December 9,2009

Question 3 in the practice questions is missing the oracle B on the right hand side. It should read A is B-recursive if and only if both A and \bar{A} are B-r.e.

Question 5 should have an "equivalent" sign on both sides of the if and only if.

### (Near) end of semester

December 3,2009

A collection of practice questions on Chapter 9 have been posted on the handouts page. If you'd like feedback on your solutions, please hand them in by December 10.

The teaching evaluation forms will be handed out in class on December 8.

### Fixed Proof System handout

December 1,2009

A corrected version of the Proof Systems handout has been fixed: the most notable change is that the first proof system presented allows all generalizations of axioms as axioms. This will be particular helpful as you work on question 4 in PS 10.

### Handouts

November 19,2009

A handouts on formal proof systems has been posted. Problem Set 10 is also up. Note that this pset is the last pset of the semester and is due on December 3. It is quite long so I suggest you start early.

### PS 9

November 14,2009

In question 2a on PS 9, you may assume that B is r.e.

### Clarifying PS 8

November 9,2009

In question 4 on PS 8, note that the algorithm for the enumeration should read ...if it halts before or immediately after the last step..." In other words, after running P_i for n steps, we output a number if and only if P_i halts in at most n steps.

Note that PS 9 is also now available.

### Files posted

November 5,2009

By popular demand, the solutions to the midterm are now posted on the handouts page.

On that page, you can also find the new problem set (PS 8, due November 12) and solutions to PS 6.

### PS 6 Erratum

October 28,2009

In the preamble before question 4 on PS6, the note gives a faulty proof that the Busy Beaver function B(n) is total. The function is, in fact, total but the proof needs to be more careful. In particular, there are infinitely many URM programs with at most n many instructions.

### Exam results

October 20,2009

The average score on the exam was 72/100.

Sample solutions are available for viewing in my office.

October 12,2009

The first exam of the course will be in class on Thursday 10/15. It covers the material up to and including the lecture on 10/8.

• Unlimited Register Machines and URM computable functions.
• Turing Machines and TM computable functions.
• Lambda calculus and lambda calculus definable functions.
• Post canonical systems and Post generable functions.
• General recursive functions.
• Equivalences between classes of functions.
• Primitive recursive functions.
• Church-Turing thesis.

I will hold special office hours this week: Tuesday 3pm-5:30pm, Wednesday 2:30pm-4:00pm.

October 1,2009

I have added a new office hour: Tuesdays 3:30pm-4:30pm.

The new problem set has been posted on the handouts page. You may want to consult the proof that all TM computable functions are general recursive for terminology used in the problem set; this proof has also been posted on the handouts page. The problem set is due at the beginning of class on Thursday 10/8.

Links to some of the original papers in the field are now available on the resources page.

Solutions are now available for pset 2.

### New files up

September 23,2009

The third problem set has been posted on the handouts page. It is due at the beginning of class on Thursday 10/1.

Solutions are now available for pset 1.

### Psets updated

September 17,2009

The second problem set has been posted on the handouts page. It is due at the beginning of class on Thursday 9/24.

Graded papers for problem set 1 will be handed back on Tuesday 9/22. Solutions for that problem set will be made available that day as well.

### First pset posted

September 10,2009

The first problem set has been posted on the handouts page. It is due at the beginning of class on Thursday 9/17.

### Welcome!

September 3,2009

Welcome to 18.511. This webpage will be your main source of information for this course. It will be updated frequently with announcements and assignments, so check back often.

The calendar on the resources page has all important dates for this course.

#### Instructor: Mia Minnes

Office: 2-172
Website: math.mit.edu/~minnes
Email: minnes@math.mit.edu

#### Lectures

TR 11:00pm - 12:30pm 2-255

#### Office Hours

T 9:30am-10:30am, T 3:30pm-4:30pm, W 2:30pm-3:30pm