These notes are mostly from 2004 but some addtions from 2007.

Lecture notes for Recursion Theorists:
recthy.tex .. recthy.pdf

Version for Computability Theorists:
cmpthy.tex .. cmpthy.pdf

Version for for those who love pineapples:
pineapp.tex .. pineapp.pdf

M773 Fall 2007 MWF 12:05-12:55 Van Vleck B131
Recommended books:
Hartley Rogers, Theory of recursive functions
Robert Soare, Recursively enumerable sets and degrees
Barry Cooper, Computability theory

DESCRIPTION: Abstract theory of computation. Turing degree and jump, strong reducibilities, arithmetic hierarchy, index sets, simple and (hyper)hypersimple sets, easy forcing arguments in computability theory, finite injury priority arguments: Friedberg-Muchnik Theorem, Sacks Splitting Theorem, existence of a maximal set. Infinite injury priority arguments: Lachlan minimal pair, Sacks density theorem, incomplete high degrees. Recursive ordinals and the hyperarithmetical hierarchy.

Homework is due in class one week from the day it is assigned.
1. (Wed 9-5) Email soare@cs.uchicago.edu and request that he email you a copy of his book.
2. (Fri 9-7) Convince yourself that every computable function is UR-BASIC computable. Write a UR-BASIC program for d=gcd(n,m).
3. (Mon 9-10) Show that the "dove-tailing" pairing function is primitive recursive.
4. (Wed 9-12) Let f(n) be the n th digit in the usual decimal expansion of the square root of 2. Prove that f is primitive recursive.
5. (Fri 9-14) Show that a UR-Basic computable function which can be computed in primitive recursive time is primitive recursive.
6. (Fri 9-14) Show that P-Basic computable is the same as primitive recursive. P-Basic has no goto's but only for-next loops. (see notes exerise 4.6.)
7. (Mon 9-17) Prove there is a computable function f whose graph is primitive recursive but f is not primitive recursive.
8. (Wed 9-19) For a partial function f suppose that each of dom(f), graph(f), and range(f), is either computable or computably enumerable but not computable. For each of the 8 possibilities, either give an example of such an f or prove it is impossible.
9. (Fri 9-21) (a) For a partial function f prove that f is partial computable iff its graph is computably enumerable. (b) For a partial computable h prove there is a partial computable g with dom(g) containing range h and for all y in range h h(g(y))= y. (c) Give an example for (b) for which g cannot be total.
10. (Mon 9-24)(a) Prove there is an e such that W_e= {0,1,2,..., e^2+1}. (b) Prove there are distinct e0 and e1 with W_e0={e1} and W_e1={e0}
11. (Wed 9-26) Prove that a c.e. set A is creative iff there exists a computable f such that (f(e) in W_e and f(e) in A) or (f(e) not in W_e and f(e) not in A) for every e.
12. (Fri 9-28) Prove or disprove: there is a creative set A and computable function f such that for any e, if W_e meets A in a finite set, then f(e) is not in A or W_e.
13. (Mon 10-1) Suppose A and B are infinite c.e. sets and A one-to-one reducible to B. Show there is a one-to-one reduction of A to B which maps A onto B.
14. (Wed 10-3) Show that for any countable set of nonzero Turing degrees there is a degree incomparable to everything in the set.
15. (Fri 10-5) Prove that: (a) For every degree c there are incomparable degree a and b which meet in 0 and join above c. (b) There are incomparable degrees a and b which meet in 0 and join in 0'.
16. (Mon 10-8) Prove that if two degrees a and b fail to have a meet then there is a strictly ascending sequence of degrees as in Spector's Theorem 21.1.
17. (Wed 10-10) Find an example of a computable binary branching subtree of finite sequences in omega with the property that it has a single infinite branch b and b is Turing equivalent to K.
18. (Fri 10-12) Prove there is a perfect tree T such that every infinite branch thru T has minimal degree.
19. (Mon 10-15) Prove that O^(omega) is not a minimal upper bound of the O^(n).
20. (Wed 10-17) Prove
(a) If A is 1-1 reducible to B and B simple then A is simple or cofinite.
(b) If A and B simple then A join B simple.
(c) If A and B simple then A intersect B simple.
(d) If A simple, b notin A, and B=A U {b}, then B <_1 A and nothing is in between.
21. (Fri 10-19) Prove that if A and B are simple incomparable with respect to 1-reducibility, then A and B have no join with respect to 1-reducibility. Hint: Use exercise 20 and 13.
22. (Mon 10-22) Prove there is a computable poset in which every countable poset can be embedded.
23. (Wed 10-24) Prove there are c.e. sets A and B which are Turing incomparable, disjoint, and cannot be separated by a computable set.
24. (Fri 10-26) Prove there is a c.e. set which is not auto-reducible. Extra Credit: make it a low simple set.
25. (Mon 10-29) (a) Suppose B is a c.e. set which is not computable. Prove there exists a partial computable function f with domain B such that for every n in omega the set f^{-1}{n} is not computable. (b) Prove or disprove. There exists A_n for n in omega pairwise disjoint c.e. sets which are not computable and partition omega.
26. (Wed 10-31) Show that if B is c.e. but not computable, then there exists disjoint c.e. sets C and D with union B which cannot be separated by a computable set. Hint: If {e} is total, show that there must be infinitely many s such that {e}_s(b_s) converges.
27. (Fri 11-2) Show there exists low c.e. sets A_0 and A_1 such that every c.e. B set is Turing equivalent to a join of c.e. sets B_0 and B_1 where B_i is computable in A_i.
28. (Mon 11-05) Put the Friedberg-Muchnik argument on a tree of outcomes. Show there is no injury on the true path.
29. (Wed 11-07) Prove there is a minimal pair A_0 and A_1 such that (a) each A_i is low. (b) A_0 and A_1 are beneath a low B.
30. (Mon 11-12) (a) Prove that truth-table reducibility is transitive. (b) Prove that if A is hypersimple and (D_x:x in C ) is a strong array, then there exists an infinite computable E subset of C such that D_x subset of A for all x in E.
31. (Wed 11-14) Suppose A is a c.e. set with infinite complement. Prove it has a hypersimple superset.
32. (Fri 11-16) Let A be a maximal set (or just hyperhypersimple). Let f be a computable map of omega 1-1 onto A. Suppose B=f(A). Prove that B is hyperhypersimple but not maximal.
33. (Mon 11-19) For each n >1 prove there are maximal sets A1,A2,...,An such that Ai not equal mod finite to Aj for distinct i and j. Prove that for any such sequence of maximal sets that E*(B) is isomorphic to the finite boolean algebra with n atoms where B is the intersection of them.
34. (Mon 11-26) Prove there is a permuation f of omega such that for every c.e. set A that f(A) is c.e. but for some c.e. set A f^-1(A) is not c.e.
35. (Wed 11-28) (Martin) Find an example of a nontrivial c.e. set which has no maximal superset.
36. (Fri 11-30) Prove that if b(0),b(1),b(2).. is the complement of a maximal set B,then for every computable f, f(b(n)) is less than b(n+1) for all but finitely many n.
37. (Mon 12-03) Suppose for every n that 0^(n) is computable in A. Prove that 0^(omega) is computable in A''.
38. (Wed 12-05) For the correct family Gamma, show that INF, EQ, EQ* are m-complete Gamma sets.