Computatability and Hierarchies

http://www.andrew.cmu.edu/user/kk3n/recursionclass/recursion.html

Current News:

Chapters 11-13 are now posted
Chapters 8-10 have been corrected
Chapter 14 has been added. That's as far as we will be going.

Syllabus

Introduction
Primitive recursion.
Indexing and diagonalization.
Grzegorczyk hierarchy.
Minimization, partial recursive functions, universal machine, 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 thoerem.
Church's thesis and Hume's problem.
Productive sets.
Turing reducibility and the Friedburg-Muchnik theorem.
The arithmetical hierarchy.
Cubbyholes
Recursive functionals.
Some basis theorems.
Learning theory applications.
Mind changes: trial-and-error hierarchy and finite difference hierarchy.
Analytical and projective hierarchies.
Determinacy and Wadge games.

Resources

Axiomatic Set Theory Primer

Basic Information:

Time: MW 11:30-12:50

Instructor: Kevin T. Kelly.

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

Phone: X8567.

Office: 135 BH.

Office hours: Mon: 3:00-4:00, Wed 1:00-2:00, 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..

Texts:
Course lecture notes available online from this page.
Hartley Rogers’ classic The Theory of Recursive Functions and Computability, MIT Press.

Nigel Cutland’s Computability, Cambridge.

Some handouts from more expensive sources that are strongly recommended to keen students for purchase.

Hierarchy theory:

H. E. Rose, Subrecursion, Oxford.

Peter Hinman, Recursion Theoretic Hierarchies, Springer.

Robert Soare, Recursively Enumerable Sets and Degrees, Springer.

I. Moschavakis, Descriptive Set Theory, North Holland.

Computational Learning Theory

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

Kevin Kelly, The Logic of Reliable Inquiry, Oxford.

Computational Complexity

Garey and Johnson, Computers and Intractability.

Level of the Course:

I assume some familiarity with basic computational models, primitive recursion, naïve set theory, and first-order logic. We will "bootstrap" computability from scratch so no substantive results will be presupposed.

Aims of the Course:

To learn something about computability and some of its applications.
To learn how to rely on metaphors to move from one hierarchy to another and to generate interesting questions to study.
To have some fun! This is an area of mathematics filled with ironic twists.

General Requirements

Participation: It's much better to talk about what you understand or don't understand. If you don't try to say it, you won't know you don't know it.

Exercises (50%) to be turned in on the due date in class. Late penalty 10% per day. To be turned in typed (for practice in producing finished mathematical documents). Good time to learn LaTex. I'll be happy to give advice. Also, the source code of the lecture notes will provide you with some examples to work with.

2 class presentations (20%).

Graduate students: a final project of some sort (30%). Due the last day of class. 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).