Computability and Learnibility

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

Current News: 

Dear Computability and Learnibility Students:

Sorry, I am returning from talks in the UK and India.  I will be in class on Thursday.  Read chapter 1 and get started on chapter 2 of the text

To avoid broken links,  go straight to the course directory at

Andrew.cmu.edu/user/kk3n/complearn.  The chapter names are obvious (e.g., chapter1.pdf).  

Best,

Kevin

Syllabus

  • Introduction
  • Computability
  • Primitive recursion.
  • Indexing and diagonalization.
  • Partial recursive functions: minimalization, universal machines, s-m-n theorem
  • Church-Turing thesis and acceptable numberings
  • Recursive and semi-recursive Relations
  • Reducibility, Rice's theorem and the Rice-Shapiro theorem.
  • The Kleene recursion theorem.
  • Demons of computability.
  • Goedel's demons
  • The arithmetical hierarchy.
  • Convergence
  • Goedel and productive sets.
  • Learnibility.
  • Hume's problem, confirmation, and performance.
  • Church's thesis and Hume's problem.
  • Verification, refutation, and convergence.
  • Counting retractions.
  • The topology of induction.
  • Application: Ockham's Razor explained.
  • Application: Taming the infinite regress.
  • Computable Learnability
  • Computable inquiry and the arithmetical complexity of  function sets.
  • Computable discovery and Gold's theorem.
  • Application: Computable science meets uncomputable theories.

Basic Information:

Time: MW10:30-11:50
Place: OSC 203

Instructor: Kevin T. Kelly.

E-mail: kk3n@andrew.cmu.edu.

Phone: X8567.

Office:135 BH.

Office hours: Mon: T 1:30, R 9:30, or by appointment.  I'm around a lot more than this and I will be happy to meet with you any time I am free..

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:

Basic Set Theory Notes


Relevant texts:

Computability theory (strongly recommended):


Hierarchy theory:

Peter Hinman, Recursion Theoretic Hierarchies, Springer.
Robert Soare, Recursively Enumerable Sets and Degrees, Springer.
I. Moschavakis, Descriptive Set Theory, North Holland.
H. E. Rose, Subrecursion, Oxford.

Computational Complexity

Garey and Johnson, Computers and Intractability.

Computational Learning Theory

Osherson et. al., Systems that Learn, MIT Press.

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


Exercises due 1-22:  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.