Math 29: Introduction to Computability

I will endeavor to give as much advance notice on homework as possible, which means I may occasionally need to move due dates later because class went more slowly than I thought. "Monday" means "I must have it upon walking into my office Tuesday morning."

  1. Due Monday, April 4: 3.2.3 (p 37), 3.3.4 (p 40), 3.1.4 (p 35), 3.4.2, 3, 4 (p 44), 3.4.5 (p 45).
         Note: on the first mini-test I may also ask you to step through a Turing machine computation as in 3.2.2; you may need to identify the function the machine computes.
     
  2. Due Monday, April 11: 4.2.1 (p 59), 4.3.2 (p 59), 4.4.5, 6, 8 (p 61), 4.5.6 (p 65), 4.5.9 (p 66).
     
  3. Due Monday, April 18: 5.2.5, 6 (p 74), 5.2.7, 9, 12, 13, 14, 17 (p 75), 5.2.18 (p 76).
     
  4. Due Monday, May 2: 5.4.2 (p 77), 6.1.4, 8 (p 80), 6.1.10 (p 81), 7.1.2 (p 91), 7.2.2 (p 92).
     
  5. Due Monday, May 9: 7.2.6, 7 (p 94), 7.2.11 (p 95), and the following:
    Define the index set Con = {e : φe is total and constant}. Show Con is Π2.
     
  6. Due Monday, May 16 (last HW): 6.2.4 (p 88) -OR- 6.2.5 (p 89) -OR- both 8.1.3 and 8.1.6 (p 98-99).

Back to main m29 page

Last modified May 1, 2011