Computability and Learnibility

http://www.andrew.cmu.edu/user/kk3n/complearn/complearn2006.html

Current News: 

The corrections to chapter 2 are now posted.  Let me know if I missed any.

Syllabus

    1. Primitive recursion.
    2. Indexing and diagonalization.
    3. Partial recursive functions: minimalization, universal machines, s-m-n theorem
    4. Church-Turing thesis and acceptable numberings
    5. Recursive and semi-recursive Relations
    6. Reducibility, Rice's theorem and the Rice-Shapiro theorem.
    7. The Kleene recursion theorem.
    8. Demons of computability.
    9. Goedel's demons
    10. The arithmetical hierarchy.
    11. Convergence
    12. Goedel and productive sets.
  1. Hume's problem, confirmation, and performance.
  2. Church's thesis and Hume's problem.
  3. Verification, refutation, and convergence.
  4. Counting retractions.
  5. The topology of induction.
  6. Application: Ockham's Razor explained.
  7. Application: Taming the infinite regress.

Basic Information:

Time: MW10:30-11:50
Place: OSC 203
Instructor: Kevin T. Kelly. Required text:
Course lecture notes available online from this page.   They are downloadable in PDF format from the HTML links in the course syllabus above. 

Resource:

Relevant texts:
Computational Complexity
Garey and Johnson, Computers and Intractability.

Level of the Course:

I assume some basic facility with computational models, recursion, set theory, and first-order logic.  We will develop computability and learnability from scratch so no substantive background is absolutely necessary.  It is more a matter of having enough background to absorb the material at the required pace. 

Aims of the Course:

      To learn something about computability and some of its applications.
To apply ideas about computability to issues in the philosophy of science and scientific method.
To learn how to rely on metaphors to move from one hierarchy to another and to generate interesting questions to study and ideas for proofs.
To have some fun!  This is an area filled with ironic twists and opportunities for novelty.

General Requirements

Participation:  I expect a lively class with questions and discussion.  I don't care for philosophy classes in which students sit silently in a church-like atmosphere taking notes.   Don't be fearful about being caught in a misunderstanding.  If you are inclined to make the mistake, so are many others, who will learn from it.  Also, there is no penalty for making honest mistakes in the class, but there is in the exercises, so it's in your interest to take chances in the discussion. 

Undergraduates:
  1. Exercises (100%) to be turned in on the due date in class.  Late penalty 10% per day.  To be typeset in LaTex format. 
  2. About Latex:  if you don't already know LaTex, learning it may be the most useful feature of the class.  It will seem clunky at first, but the learning curve is steep and once you get it there is no better, faster, easier, or better-looking way to produce a technical paper.  Also, be advised that most logic, math, and science journals now require LaTex manuscripts, so you're going to have to learn it sooner or later.  HSS computing now supports LaTex.  Ask to borrow their CD to install it.   I recommend the Winedt Latex editor for producing Latex code, as it highlights the Latex commands and automatically applies the Latex processor to your code by just hitting a button.  Winedt costs only $30.00 and can be downloaded and installed immediately as shareware from this site:  Winedt.   Be careful not to confuse Winedt with Winedit, which is a useless, expensive editor (I almost bought it by mistake once). 

Graduates:

  1. Exercises (60%)  (cf. undergraduate requirements).
  2. 1 presentation (10%)
  3. a final project of some sort (30%).  Due the last day of class.  Should be around 5-10 pages at most.  Can be a short historical survey of the development of some part of the theory, a philosohical application, or some interesting exercise solutions (around 10).  You will talk to me about your project as it develops.  I'll expect you to have som idea by midterm so you have time to think about it properly.  

 

Reading and Exercise Assignments

Reading for 1-19 :
Chapter 1: Introduction
Chapter 2: Primitive Recursion

Exercises due 1-26:  Exercises 2.1, 2.2, 2.3, 2.4, 2.5, 2.7. 
LaTex exercise template for cutting and pasting into.
LaTex source code for chapter 2 for cutting and pasting math formats.