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