Math 29 Homework Schedule

I have learned throughout my life as a composer chiefly through my mistakes and
pursuits of false assumptions, not by my exposure to fonts of wisdom and knowledge.
Igor Stravinsky

Class participation is an essential part of the course; mathematics is not a spectator sport. For this section, class participation consists of reading assignments, quizzes, homework problems, and class presentations.

Reading Assignments

Reading assignments will be given daily and should be read before coming to class. For some of my thoughts on reading mathematics texts, click here.

Quizzes

Quizzes will be administered at the end of class on Monday covering material presented in lecture the previous week. They will consist of a couple of questions and should only take 10 - 15 minutes to complete. If you do the homework for the lectures given the previous week (including Friday's homework), then you should do fine on the quizzes.

Homework Problems

Homework problems will be assigned daily and collected the following class period. Late homework will not be accepted and a grade of 0 will be assigned (of course, exceptions can be made for emergencies such as illness, death, natural disasters...).

I will grade your homework and return it as soon as possible, typically the following class period. The solutions you present must be coherent and written in complete sentences whenever possible. Simply stating answers or turning in garbled, unclear solutions will result in a grade of 0. Homework will be graded on a 3 point scale: 3 = correct, 2 = mostly correct, 1 = mostly incorrect, 0 = missing.

Class Presentations

You will be asked to present a couple of proofs in class. You will be given a few options to choose from and will have plenty of time to prepare. I would expect to meet with you before your presentation to discuss the proof and any details or questions you might have.

The Schedule

On the remainder of this page you will find schedule for the course, including reading assignments, quiz dates and homework assignments. Eventually, there will also appear some information concerning the exams.

Date Lecture/Quiz Homework
3/29 Lecture 1 on Chapter 1.1 - 1.2
Algorithms and URMs 		Homework 1 due 3/31
3/31 Lecture 2 on Chapter 1.3 - 1.4
URM-computable functions and Decidability 		Homework 2 due 4/1
4/1 Lecture 3 on Chapter 2.1-2.2
The basic functions and Joining programs 		Homework 3 due 4/5
4/5 Lecture 4 on Chapter 2.3 Substitution Homework 4 due 4/7
Quiz 1 on Chapter 1.1 - 2.1
4/7 Lecture 5 on Chapter 2.4 Recursion Homework 5 due 4/9
4/9 Lecture 6 on Chapter 2.4-2.5
Recursion and Minimalization 		Homework 6 due 4/12
4/12 Lecture 7 on Chapter 2.5, 3.1, 3.2
Minimalization and Partial Recursive Functions		 Homework 7 due 4/14
Quiz 2 on Chapter 2.2 - 2.5
4/14 Lecture 8 on Chapter 3.3, 3.4
Primitive Recursion and Turing Machines 		Homework 8 due 4/16
4/16 Lecture 9 on Chapter 3.4, 3.7
Turing Machines and Church's Thesis 		Homework 9 due 4/19
4/19 Lecture 10 on Chapter 4.1, 4.2
Numbering programs and functions		 Homework 10 due 4/21
Quiz 3 on Chapter 2.5 - 3.4
4/21 Lecture 11 on Chapter 4.2, 4.3
Numbering fuctions and the Diagonal Method 		Homework 11 due 4/23
4/22 Lecture 12 on Chapter 4.4
The s-m-n Theorem 		Suggested Homework 12
4/23 Lecture 13 on Chapter 5.1, 5.3
Universal Programs and Applying the s-m-n
4/26 Lecture 14 on Chapter 5.1, Ch 5 Appendix
Universal Programs and their computability		 Suggested Homework 14
4/28 Lecture 15 on Chapter 5.1, Ch 5 Appendix, 5.2
Universal Programs: computability and applications
4/30 Submit Midterm Exam to John Hamman in Room 1J
5/3 Lecture 16 on Chapter 6.1
Undecidability in computability 		Homework 16 due 5/5
5/5 Lecture 17 on Chapter 6.1,2
Undecidability in computability, group theory		 Homework 17 due 5/7
5/7 Lecture 18 on Chapter 6.2,3,4,5
More Undecidability 		Homework 18 due 5/10
5/10 Lecture 19 on Chapter 6.6
Partial Decidability		 Homework 19 due 5/12
Quiz 4 on Lectures 16 - 18
5/12 Lecture 20 on Chapter 6.6
Partial Decidability 		Homework 20 due 5/14
5/14 Lecture 21 on Chapter 7.1, 7.2
Recursive and r.e. sets 		Homework 21 due 5/17
5/17 Lecture 22 on Chapter 7.2
R.e. sets		 Homework 22 due 5/19
Quiz 5 on Lectures 19 - 21
5/19 Lecture 23 on Chapter 7.3
Productive and creative sets 		Homework 23 due 5/21
5/21 Lecture 24 by Joel Hamkins
Infinite Time Turing Mahines		 Homework 24 due 5/24
5/24 Lecture 25 on Chapter 7.4
Simple sets 		Homework 25 due 5/26
Quiz 6 on Lectures 22 - 24
5/26 Lecture 26 on Chapter 7.4 and 9.4
Simple sets and URMOs		 Homework 26 due 5/28
5/28 Lecture 27 on Chapter 9.4 and 9.5
Relative Computabilty and Turing degrees		 No homework...
5/31 Lecture 28 on 9.5
Post's Problem		 No homework...