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