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...