Homework

Written homework assignments

The weekly written homework assignments will be posted here.

  • Written homework will be due by end of the day on Wednesdays. You may submit it in class, to my mailbox or slide it under my door. So long as I have it when I get to the department on Thursday, this is fine.
  • Make sure that you show all your work and explain all the steps. A correct answer with no work shown will receive minimal credit. This is good practice for what will be expected on exams.
  • Make sure your homework is neatly written. If you typeset your solutions in LaTeX, this is fine (indeed I would encourage it), but I will require (1) a printed copy, and (2) an email containing your source file. An emailed PDF or- worse! - just an emailed .tex file will not be be accepted.

Homework Assignments

Week of March 27-31

  • Written homework: PDF

    Monday:

    • Read: Chapter 1
    • Topics: Introduction and history

    Wednesday:

    • Read: Sections 2.1-2.2
    • Topics: Recursive functions

    Friday:

    • Read: Section 2.3
    • Topics: More on recursive functions; URMs

    Week of April 3-7

  • Written homework: PDF

    Monday:

    • Read: Sections 2.2-2.3
    • Topics: Recursive functions are URM-computable
    • File: My program for primitive recursion
    • Do ahead: Read about Turing machines and attempt Exercise 2.4.8

    Wednesday:

    • Read: 2.4-2.5
    • Topics: Turing machines and Church's thesis

    Friday:

    • Read: Chapter 3
    • Topics: First-order logic

    Week of April 10-14

  • Written homework: PDF

    Monday:

    • Read: 4.1-4.2
    • Topics: Coding Turing machines

    Wednesday:

    • Read: 4.3-4.5
    • Topics: Universal Turing machine

    Friday:

    • Read: 5.1-5.2
    • Topics: Uncomputable sets

    Week of April 17-21

  • Written homework: PDF

    Monday:

    • Read: 5.3-5.4
    • Topics: Halting sets and the busy beaver function

    Wednesday:

    • Read: 6.1-6.3
    • Topics: Creative sets and other incomputable sets

    Friday:

    • Read: 6.2
    • Topics: Priority arguments and simple sets

    Week of April 24-28

    Monday:

    • Topics: Review for the midterm

    Wednesday:

    • Topics: Midterm

    Friday:

    • Read: 6.3
    • Topics: Hilbert's 10th problem

    Week of May 1-5

  • Written homework: PDF

    Monday:

    • Read: 7.1
    • Topics: Many-to-one reducibility and posets

    Wednesday:

    • Read: 7.2
    • Topics: Many-to-one degrees

    Friday:

    • Read: 7.3
    • Topics: More on creative sets and the c.e. universe

    Week of May 8-12

  • Written homework: PDF

    Monday:

    • Read: 10.1-10.3
    • Topics: Turing reducibility and Turing degrees

    Wednesday:

    • Read: 10.4
    • Topics: C.e. degrees and the jump

    Friday:

    • Read: 10.6
    • Topics: Structure of the c.e. degrees