Problem Sets
Mathematics 114A
Problem Set I, for 1/16/07
Page 123.
- #3. Try to keep the program short.
- #4. (RM program for x - y)
Page 217
Problem Set II, for 1/23/07
Page 217.
- #9. (x/y is PR)
- #12. (sequence numbers)
Page 315
- #1 (Gödel numbers and indices)
- #2 (function number 0)
Problem Set III, for 1/30/07
Page 315.
- #3. (finding index of constant function)
Page 408.
- #1 (no computable set between Tot and K)
- #2 (range of increasing function)
- #3 (infinite computable subset of infinite c.e. set)
Problem Set IV, for 2/6/07
Page 414.
- #7 (finding index for union of c.e. sets)
- #9 (Tot reducible to Inf)
Problem Set V, for 2/13/07
Pages 414-415.
- #10 (reducibility problem)
- #11 (diagonalization problem)
- #13 (equality for c.e. sets is undecidable)
Pages 510-511.
- Either #1 or #2 (m-degrees of computable sets)
Problem Set VI, for 2/20/07
Page 517.
- #5 (computing relative to H)
- #6 (computing relative to oracle)
- #8 (complement of Tot is c.e. relative to K)
- #9 (non-transitivity of relative c.e.)
Problem Set VII, for 2/27/07
Page 606.
- #1 (classification in arithmetical hierarchy)
- #2 (classification in arithmetical hierarchy)
- #3 (Tot is complete Pi-2 set)
Note: There is no problem set due on Tuesday,
March 6. The midterm will be returned in discussion section that day.
Problem Set VIII, for 3/13/07
Page 614.
- #4 (productive sets)
- #5 (productive sets)
- #6 (creative sets)
- #8 (computing in PR time)
Here is a link to
solutions
for these problems.