Instructor: Dr Benedikt Löwe
Time: Thursday 3-5
First Lecture: September 11th, 2003
(Note that there will be no lecture on September 4th due to the
traditional Introductory Boat Trip of the Master of Logic
program. Also, there will be no lecture on October 23rd.)
Course language: English
Intended Audience: MoL students, Mathematics students in their fourth
Prerequisites: This course assumes basic mathematical skills and some
knowledge of basic logic.
This course will cover the basic notions of computability: Turing
machines, recursivity and computer programs. The Equivalence Theorem will
lead to Church's Thesis. Having a formalization of computability allows us
now to investigate the boundaries of computation: what problems are not
computationally solvable? This question will lead us to Turing's Halting
Problem and the Decidability. We discuss several notions of recursion
theoretic reducibility, their derived degree structures, and mathematical
properties of these structures.
We shall mostly follow Part A of the textbook
Robert I. Soare, Recursively Enumerable Sets and Degres,
A Study of Computable Functions and Computably Generated Sets,
In particular, we'll cover the following topics:
- Recursive Functions (Soare, Chapter I): Primitive Recursive
Functions, Turing Machines, Kleene Normal Form Theorem, Enumeration
Theorem, s-m-n Theorem, The Halting Problem, Reducibilities, Rice's
Theorem, Myhill's Isomorphism Theorem
- Fundamentals of Recursively Enumerable Sets (Soare, Chapter II):
Basic Properties, Indices, The Recursion Theorem, Completeness
- Turing Reducibility (Soare, Chapter III): Relative Computability,
Turing Degrees, the Jump operator, Delta02
- The Arithmetical Hierarchy (Soare, Chapter IV): Definitions and
Techniques, Post's Theorem, the Hierarchy Theorem,
Sigma0n complete sets, the relativized
- Gödel's Incompleteness Theorem
Topics covered so far:
- 1st Lecture (September 11, 2003). Basics of the history of computing.
Alternative models of computation. Primitive recursive functions. The diagonalization
theorem. (Up to p.10 in Soare's book.)
- 2nd Lecture (September 18, 2003). The mu operator.
Recursive functions. Derivations of recursive functions. Turing machine
architecture. Coding of the Turing machine architecture as natural
numbers. (Up to p.14 in Soare's book.)
- (September 25, 2003). Cancelled due to
- 3rd Lecture (October 2nd, 2003). Equivalence of recursive
and Turing-computable functions. Padding Lemma. Kleene Normal Form
Theorem. Enumeration Theorem. s-m-n Theorem.
(Up to p.16 in Soare's book.)
- 4th Lecture (October 9th, 2003). Recursively enumerable sets.
The Halting Problem. Undecidability of the Halting Problem.
Recursion-theoretic reductions. 1-degrees and m-degrees.
Index sets. Rice's Theorem. (Up to p.21 in Soare's book.)
- 5th Lecture (October 16th, 2003). Structure of the
1-degrees and m-degrees. Myhill's Isomorphism Theorem.
Co-r.e. sets. Finite approximations.
The degrees of Inf and Fin. The Recursion Theorem. (Completing Chapter
I, with some parts of II.1 and II.3.)
- (October 23rd, 2003). Exam week. No classes.
- 6th Lecture (October 30th, 2003). Proof of the Recursion Theorem.
The formal language of arithmetic and its Gödelization.
Sigma01 and recursive enumerability. Uniformization
Theorem. (Pages 27-29 and 60-61 in Soare's book.)
- 7th Lecture (November 6th, 2003). Listing Theorem.
Reduction Principle for r.e. sets.
Provability. Complexity of Truth. Gödel's First Incompleteness
Theorem. (Pages 29-30 in Soare's book plus additional material.)
- 8th Lecture (November 13th, 2003). Upper complexity bounds for
concrete sets. Relative computation. Turing reducibility. Oracle machines.
(Pages 61-63 and pages 46-48 in Soare's book.)
- 9th Lecture (November 20th, 2003). Relativized Normal Form Theorem.
Relativized Enumeration Theorem. Relativized s-m-n Theorem. Finite Approximations
to oracles. Use Principle. Master Enumeration Theorem. The upper-semilattice of
Turing Degrees. The upper-semilattice of r.e. degrees.
(Pages 48-50 and pages 52-53 in Soare's book.)
- 10th Lecture (November 27th, 2003).
Relativized Normal Form
Theorem for Sigma01 sets. Jump Theorem.
The jump operator on the Turing degrees.
(Pages 53-54 in Soare's book.)
- 11th Lecture (December 4th, 2003).
Relativized Arithmetical Hierarchy. Post's Theorem. Hierarchy Theorem.
Equivalence of Fin and 0''. High and low degrees.
(Pages 64-66 and 69-71 in Soare's book.)
- 12th Lecture (December 11th, 2003). Productive Sets. Immune Sets.
Simple Sets. Post's Problem. Post's Solution.
(Pages 40-43 and 77-78 in Soare's book.)
- (December 18th, 2003). Exam week. No classes.
- Homework Assignment #1 (Primitive recursive functions).
Deadline: September 18th, 2003. Soare, Exercises I.2.4 and
- Homework Assignment #2 (Turing Machines).
Deadline: September 25th, 2003. Soare, Exercises I.2.9 and
- Homework Assignment #3 (Kleene's Basic Results).
Deadline: October 9th, 2003. PDF-File.
- Homework Assignment #4 (1-degrees and m-degrees).
Deadline: October 16th, 2003.
Soare, Exercises I.4.17, I.4.18, and I.4.23 (a)-(b) (p.22/23).
- Homework Assignment #5 (Unsolvable problems and the Recursion Theorem).
Deadline: October 30th, 2003.
PDF-File [including Soare,
Exercises I.4.24 and I.4.27
- Homework Assignment #6 (Separability and recursive images and
Deadline: November 6th, 2003.
Soare, Exercises I.4.22(a) (p.23), II.1.17 and II.1.23 (p.32).
- Homework Assignment #7 (Coding language into arithmetic).
Deadline: November 13th, 2003.
- Homework Assignment #8 (Calculating complexities).
Deadline: November 20th, 2003. Soare, Exercises IV.1.10 and IV.1.12
- Homework Assignment #9 (Turing degrees).
Deadline: November 27th, 2003. Soare, Exercises III.2.6 and III.2.7
- Homework Assignment #10 (The Turing jump).
Deadline: December 4th, 2003.
- Homework Assignment #11 (High and Low degrees).
Deadline: December 11th, 2003.
Soare, Exercises IV.4.5 (a) and (b) and IV.4.6 (b)
Extra Credit Assignments:
The idea of Extra Credit Assignments is to give you an opportunity to
develop mathematical ideas of your own beyond the limited scope of a
homework exercise. They are vaguely formulated and give you the chance
to develop the proper definitions needed to prove the desired results.
extra credit assignments are supposed to be an exercise in mathematical
writing as well, so please try to hand them in in the style of textbook
mathematics: definitions, lemmas, claims and theorems should be
clearly marked as such, proofs should be marked
by the word ``Proof'' and some marker that tells the reader that the proof
is finished. LaTeXed solutions are strongly preferred for the extra credit
Extra Credit Assignments have no effect on the question whether you
or fail the course. They can have a positive effect on your final grade,
- Extra Credit Assignment #1 (Primitive recursive functions).
Deadline: Thursday, October 16, 2003.
In an informal way, primitive recursive
relations are ``closed under propositional connectives''. Give a formal
definition of that notion and prove the corresponding theorem.
- Extra Credit Assignment #2 (WHILE computability).
Deadline: Tuesday, October 28, 2003.
You hear very often that recursive functions are equivalent to something
called ``WHILE computability'' (referring to an unbounded search
loop in usual programming languages). Give a proper formalization of
WHILE computability by inventing a syntax for an
artificial programming language and prove that this notion is equivalent
- Extra Credit Assignment #3 (Relativized Normal Form Theorem).
Deadline: Thursday, December 4, 2003.
Develop a coding of oracle machines as natural numbers and a relativized
Kleene T-predicate and prove the relativized Normal Form Theorem.
If you don't like Soare's version of oracle machines, feel free to give
your own definition, but make sure that you properly state it before
you start the formalization. If you're interested, you can go on and use
version of the Normal Form Theorem to prove the relativized Enumeration
Theorem and the relativized s-m-n Theorem.
Written Exam. The following is a possible written exam designed for 120 to 180 minutes. If you
want, you can do it for training purposes:
Last update : February 5th, 2004