18.511

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.

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

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.

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.

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.

The average score on the exam was 72/100.

Sample solutions are available for viewing in my office.

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.

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.

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.

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.

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

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.