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.
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.
Here are some recommended readings on algorithmic randomness.
t20@psu.edu / 20 December 2007