Mathematics 114C, Computability Theory, Winter 2019, HW


In solving a problem, you may assume and use every result and problem which appears before it in the Notes. You are also encouraged to seek help with the homework from either the instructor or the TA.

Optional problems are exactly what the words say: you do not have to hand them in and they will not be taken into account in computing your basic grade for the class. Work on them if they catch your interest, and do not hesitate to ask for help with them if you need it.
HW #8, due Thursday, March 14: x4D.3, x4D.8, x5A.4, x5A.5, x5A.6, x5A.7, x5A.9, x5A.10.        Solutions
HW #7, due Thursday, March 7: x4C.1, x4C.2, x4C.3, x4D.1, x4D.2, x5A.1, x5A.2, x5A.3.        Solutions
HW #6, due Thursday, Feb 21: x3A.7, x4B.8, x4B.9, x4B.10, x4B.11,
Extra problem 1. Prove that if A and B are both recursive, infinite and with infinite complements, then there is a permutation h of the natural numbers such that h[A]=B.
Optional x2D.3.        Solutions
HW #5, due Friday Feb 15: x4A.2, x4A.3, x4B.1, x4B.2, x4B.3, x4B.4, x4B.5, x4B.6.
Optional. x4B.7.        Solutions
HW #4, due Thurs Feb 7: x3A.1, x3A.2, x3A.3, x3A.5, x3A.6, x3A.8.        Solutions
HW #3, due Wed. Jan 30, in class: x2B.3, x2B.5, x2B.6, x2B.7, x2B.9, x2B.10.
Optional. x2B.8.        Solutions
HW #2, due Thurs Jan 24: x1C.2, x1C.8, x1C.9, x1C.10, x2A.1, x2A.2, x2A.3, x2A.4.
Optional. x1B.24, x1C.12.        Solutions
HW #1, due Thurs Jan 17: x1A.4, x1A.6, x1A.9, x1A.11, x1A.12, x1B.4, x1B.10, x1B.16, x1B.18.       Check Here.
Optional. x1A.10, x1B.19.        Solutions