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

• Topics: Introduction and history

#### Wednesday:

• Topics: Recursive functions

#### Friday:

• Topics: More on recursive functions; URMs

### Week of April 3-7

• Written homework: PDF

#### Monday:

• Topics: Recursive functions are URM-computable
• File: My program for primitive recursion

#### Wednesday:

• Topics: Turing machines and Church's thesis

#### Friday:

• Topics: First-order logic

### Week of April 10-14

• Written homework: PDF

#### Monday:

• Topics: Coding Turing machines

#### Wednesday:

• Topics: Universal Turing machine

#### Friday:

• Topics: Uncomputable sets

### Week of April 17-21

• Written homework: PDF

#### Monday:

• Topics: Halting sets and the busy beaver function

#### Wednesday:

• Topics: Creative sets and other incomputable sets

#### Friday:

• Topics: Priority arguments and simple sets

### Week of April 24-28

#### Monday:

• Topics: Review for the midterm

#### Wednesday:

• Topics: Midterm

#### Friday:

• Topics: Hilbert's 10th problem

### Week of May 1-5

• Written homework: PDF

#### Monday:

• Topics: Many-to-one reducibility and posets

#### Wednesday:

• Topics: Many-to-one degrees

#### Friday:

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

### Week of May 8-12

• Written homework: PDF