Math 497A is an unusual 4-credit course which I taught in Fall 2007. It was part of MASS, our special program for high-achieving undergraduate mathematics majors from around the USA. The material was also of interest to other advanced undergraduate and graduate students in mathematics and related disciplines.

The title of the course was **Computability, Unsolvability,
Randomness**. The course included an introduction to Turing's
theory of computability and unsolvability. This material is basic for
theoretical computer science and for the study of unsolvable
mathematical problems. In addition, the course included an
introduction to a research area which is currently very active:
algorithmic randomness and Kolmogorov complexity.

Class meetings were Monday, Wednesday, Thursday, and Friday, 10:10 - 11:00 AM, in 113 McAllister. The teaching assistant was Jonas Kibelbek. Each student was required to perform a research project. A preliminary list of suggested projects is below. There were weekly homework assignments due every Monday, a written midterm exam on Wednesday October 3, and individual oral final exams during the week of December 10-14. In addition, each student handed in a 5-10 page written report on his/her research project.

The schedule number of this course was 857722.

My office is 305 McAllister. Students in this course were encouraged to drop in whenever my door was open, or make an appointment.

Each student took a 1-hour oral final exam. The exam consisted of one QUESTION, one PROBLEM, and a brief report on the student's research project. The QUESTIONS were chosen from the list below. The PROBLEMS were not known in advance, but they were similar to homework problems or midterm exam problems.

Here are some course materials.

- Syllabus: PDF, PS, DVI.
- Lecture notes: PDF, PS, DVI.
- Suggested projects: PDF, PS, DVI.
- Collaboration policy: PDF, PS, DVI.
- Homework #1, due Tuesday September 4: PDF, PS, DVI.
- Homework #2, due Monday September 10: PDF, PS, DVI.
- Homework #3, due Monday September 17: PDF, PS, DVI.
- Homework #4, due Monday September 24: PDF, PS, DVI.
- Homework #5, due Monday October 1: PDF, PS, DVI.
- Midterm Exam, Wednesday October 3: PDF, PS, DVI.
- Homework #6, due Monday October 8: PDF, PS, DVI.
- Homework #7, due Monday October 15: PDF, PS, DVI.
- Homework #8, due Monday October 22: PDF, PS, DVI.
- Homework #9, due Monday October 29: PDF, PS, DVI.
- Homework #10, due Monday November 5: PDF, PS, DVI.
- Homework #11, due Monday November 12: PDF, PS, DVI.
- Homework #12, due Monday November 26: PDF, PS, DVI.
- Homework #13, due Monday December 3: PDF, PS, DVI.
- Assigned projects, due Monday December 10: PDF, PS, DVI.
- Questions for Final Exam, Monday-Friday December 10-14: PDF, PS, DVI.
- Final Exam Schedule.

Here are some recommended textbooks and lecture notes on computability and unsolvability. The textbooks were placed on reserve in the Physical and Mathematical Sciences Library, 201 Davey. Note that Davey Lab is across the street from McAllister Building.

- Hartley Rogers, Jr., Theory of Recursive Functions and Effective Computability.
- Piergiorgio Odifreddi, Classical Recursion Theory, Volumes I and II.
- Manuel Lerman, Degrees of Unsolvability.
- Robert I. Soare, Recursively Enumerable Sets and Degrees.
- Lecture notes from my course on Foundations of Mathematics. (123 pages. Chapter 1 is an introduction to computability and unsolvability.)
- Lecture notes from my topics course, Spring 2004. (104 pages. Chapter 1 is an introduction to computability in core mathematics. Chapter 2 is an introduction to degrees of unsolvability.)
- Lecture notes from my topics course, Spring 2005. (89 pages. Chapter 1 is an exposition of the unsolvability of Hilbert's Tenth Problem. Chapter 2 is an exposition of the unsolvability of the word problem for groups. Sections 3.10 and 3.11 are an introduction to Turing reducibility. Chapter 4 is an introduction to algorithmic randomness.)

Here are some recommended readings on algorithmic randomness.

- Lecture notes by Peter Cholak. (69 pages.)
- Book in preparation, by Rod Downey and Denis Hirschfeldt. (>500 pages.)
- Book in preparation, by Andre Nies. (>240 pages.)
- My semi-expository paper
*Almost everywhere domination and superhighness*. (28 pages.)

t20@psu.edu / 20 December 2007