Undecidability and Incompleteness

LPS/Phil 105C/205C
Tu Th 12:30 - 1:50
SSL 105 
Spring, 2008

Homework and notes
         

Basic Information
Instructor:  Kent Johnson
Office Hours:  right after class, and by appointment
Office Location:  SST 755

Required Text:  We will continue to use the same notes as in the A and B components of this sequence. If you do not already have a copy of them, please let me know. 

Course Password: ___________________________________
Other Resources: A former student in this course has recommended the following two books, as potentially useful ancillary resources:

Test Dates
Midterm:  TBA
Final:  TBA 

General remarks.  Welcome to the third component of the LPS logic sequence. Our primary goal will be to prove a handful of related theorems regarding the boundaries of formal computation. These theorems include Gödel's first and second incompleteness theorems and Church's theorem. At one time, it was thought that we should be able to formalize any question whatsoever, and with suitable mathematical cleverness, devise an algorithm for answering that question. For instance, the philosopher and mathematician G. W. Leibniz thought that the progress of mathematics would be such that

'when controversies arise, there will be no more need for a disputation between two philosophers than there would be between two accountants. It would be enough for them to pick up their pens and sit at their abacuses, and say to each other . . .: "Gentlemen, let us compute!"' (untitled, undated note, GP.VII.200)

What does such a view amount to? Can we make sense out of it in mathematically rigorous terms? To the extent that we can, does the view remain true? What does it mean to 'compute' the answer to a question, anyways? On our way to proving the central theorems of the course, we will address these questions carefully.

Material to be Covered. You are expected to read all of Part III of Logic for Philosophers. In class, we will cover sections: 1, 2.0, 2.1, 2.2 (informally), 2.3, 2.4, 2.5, 3.1, 3.2, 3.4, 5.1 (informally), 5.2 (via Löb’s theorem). Time permitting, we will examine some further related issues.

Grading.  Your grade for the course will be based on a 1000 point scale.  Homework and the midterm will be worth 600 points total, and the final will be worth  400 points. The grading scale for the course will be as follows:

900 ­ = A
850 ­ = B+
800 ­ = B
750 ­ = C+
700 ­ = C
650 ­ = D+
600 ­ = D
below 600 = F
 
   

Homework
Homework #1
Homework #2
Homework #3
Homework #4
 Notes
Notes on the Fundamental Theorem of Arithmetic and coding
Notes on Turing Machines
Notes on the definability theorem

   

Hints, Comments, Etc.

  • Homework 1:
    • Feel free to use the "informal" (*ed) definitions. We won't ever replace them. Rather we'll later see how Church's Thesis legitimates them, in a certain specific sense.
    • Also feel free to appeal to an operation of "Shift the sequence n spaces to the left (or right)", as a generalization of what we did in class. (Remember that the Turing machine performs this by starting at the leftmost edge of the sequence.)






This syllabus has welcomed viewers with open arms.

Home